On dual Eulerian paths and circuits in plane graphs
S. Ueno, Katsufumi Tsuji, Yoji Kajitani · 2003
Given a nonseparable plane graph G, a path or circuit is called dual if it is also a path or circuit, respectively, in the geometric dual of G. Motivated by a layout design problem of CMOS integrated circuits, the authors consider some problems of partitioning the edges of G into the minimum number of dual paths or circuits. The results include a constructive proof of the fact that the following problems are solvable in polynomial time: determining whether G has a dual circuit; finding a dual Eulerian path or circuit if one exists; and finding the minimum set of dual paths that partitions the edges of G when G has no dual circuits.>