ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Discussiones Mathematicae Graph Theory 16(2) (1996)
197-205 DOI: 10.7151/dmgt.1034
R. Bruce Richter
Department of Mathematics and Statistics, Carleton
Ottawa Canada K1H 8H1
Using a Δ-matroid associated with a map, Anderson et al (J.
Combin. Theory (B) 66 (1996) 232-246) showed that one can decide in polynomial
time if a medial graph (a 4-regular, 2-face colourable embedded graph) in the sphere,
projective plane or torus has two Euler tours that each never cross themselves and never
use the same transition at any vertex. With some simple observations, we extend this to
the Klein bottle and the sphere with 3 crosscaps and show that the argument does not work
in any other surface. We also show there are other Δ-matroids
that one can associate with an embedded graph.
Keywords: Δ-matroids, graph embeddings, A-trails.
1991 Mathematics Subject Classification: 05C10, 05B35.