Author: Brigitte Servatius and Herman Servatius

Reference: Discrete Mathematics 244, pp 445-454, 2002.

Selected Figures:

Abstract: 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 with exponentially 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.