ORTHOGONAL A-TRAILS OF 4-REGULAR GRAPHS EMBEDDED IN SURFACES OF LOW GENUS

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 pla ne 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 gr aphs in the projective plane and the torus, and the related problem of deciding when a 2-regular digraph contains two orthogonal Euler trail s. (C) 1996 Academic Press, Inc.