Orthogonal A-Trails of 4-Regular Graphs Embedded in Surfaces of Low Genus

✍ Scribed by Lars Døvling Andersen; André Bouchet; Bill Jackson

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 390 KB
• Volume: 66
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1996.0017

✦ Synopsis

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 characterise 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 exists. 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.

1996 Academic Press, Inc.

1. Introduction

We shall consider finite graphs which may contain multiple edges but no loops. We shall refer to graphs which may contain loops as pseudographs. A graph is Eulerian if it is connected and all vertices have even degree. Given a plane representation of an Eulerian graph G, an A-trail of G is an Euler trail in which any two consecutive edges, say v i&1 v i and v i v i+1 , are article no. 0017 232 0095-8956Â96 18.00