A Polynomial Time Algorithm for Determining Zero Euler-Petrie Genus of an Eulerian Graph

A dual-Eulerian graph is a plane graph which has an ordering defined on its edge set which forms simultaneously an Euler circuit in the graph and an Euler circuit in the dual graph. Dual-Eulerian graphs were defined and studied in the context of silicon optimization of cmos layouts. They are necessarily of low connectivity, hence may have many planar embeddings. We give a polynomial time algorithm to answer the question whether or not a planar multigraph admits an embedding which is dual-Eulerian and constructs such an embedding, if it exists