A-trails of embedded graphs and twisted duals - Yan, Qi (Ars mathematica contemporanea, 2022)
Kotzig showed that every connected 4-regular plane graph has an ?$A$?-trail -- an Eulerian circuit that turns either left or right at each vertex. However, this statement is not true for Eulerian plane graphs and determining if an Eulerian plane graph has an ?$A$?-trail is NP-hard. The aim of this paper is to give a characterization of Eulerian embedded graphs having an ?$A$?-trail. Andersen et al. showed the existence of orthogonal pairs of ?$A$?-trails in checkerboard colourable 4-regular graphs embedded on the plane, torus and projective plane. A problem posed in their paper is to characterize Eulerian embedded graphs (not necessarily checkerboard colourable) which contain two orthogonal ?$A$?-trails. In this article, we solve this problem in terms of twisted duals. Several related results are also obtained.
Keywords: A-tir; A-trails; checkerboard colourable; embedded graphs; Eulerian; Eulerjev obhod; šahovnično pobarvljiv; twisted duals; vloženi grafi; zasukani duali