A polynomial time algorithm for determining zero Euler-Petrie genus of an Eulerian graph (Q1349112): Difference between revisions

An Euler-Petrie walk in a graph embedded in some orientable surface is an Euler path which is also a Petrie walk (i.e., it alternates between left and right turns at successive vertices). A plane graph has an Euler-Petrie walk if and only if it is dual-Eulerian, that is, it has an Euler circuit which is also an Euler circuit of its dual. Any Eulerian graph can be embedded in some orientable surface so that it has an Euler-Petrie walk; the Euler-Petrie genus of an Eulerian graph is the smallest genus of such a surface. In the present paper, the authors present a polynomial-time algorithm for deciding whether a given Eulerian graph has Euler-Petrie genus zero. For this, it is sufficient to consider only graphs which are two-connected. The main idea is to decompose a two-connected graph into its three-block tree (analogous to the block-cutpoint tree), and to apply an inductive procedure that ``prunes'' this tree one pendent node at a time. The difficulty is that a planar graph with more than one three-block may have a number of planar embeddings which is exponential in the number of edges. Thus, no polynomial-time algorithm can consider all possible embeddings. The authors reduce the number of embeddings that need to be considered by examining the different ways an Euler-Petrie circuit may pass from one three-block to another.