Orthogonal A-trails of 4-regular graphs embedded in surfaces of low genus
type: Item
instance of: scholarly article
title: Orthogonal A-trails of 4-regular graphs embedded in surfaces of low genus
zbMATH Open document ID: 0855.05047
author: Lars Døvling Andersen
author: André Bouchet
author: Bill Jackson
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-01-12T00:00:00Z
review text: Anton Kotzig has shown that every connected 4-regular plane graph has an A-trail, that is an Euler trail in which any two consecutive edges lie on a common face boundary. We shall characterize the 4-regular plane graphs which contain two orthogonal A-trails, that is to say two A-trails for which no subtrail of length 2 appears in both A-trails. Our proof gives rise to a polynomial algorithm for deciding if two such A-trails exist. We shall also discuss the corresponding problem for graphs in the projective plane and the torus, and the related problem of deciding when a 2-regular digraph contains two orthogonal Euler trails.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 934790
zbMATH Keywords: embedding in surfaces
zbMATH Keywords: delta-matroid
zbMATH Keywords: transition system
zbMATH Keywords: A-trail
zbMATH Keywords: projective plane
zbMATH Keywords: torus
zbMATH Keywords: digraph
zbMATH Keywords: orthogonal Euler trails
MaRDI profile type: Publication
full work available at URL: jctb.1996.0017
OpenAlex ID: W1978437601
DOI: 10.1006/JCTB.1996.0017
description: scientific article; zbMATH DE number 934790