dualEulerian

DualEulerian is a concept in graph theory relating to planar graphs and their duals. For a plane graph G, the dual G* is constructed by placing a vertex in each face of G and joining two vertices with an edge whenever the corresponding faces share an edge in G. G* is Eulerian when every vertex of G* has even degree and G* is connected. A graph G is called dual-Eulerian if its dual G* is Eulerian.

In terms of the original graph, a vertex of G* has degree equal to the length of the corresponding face boundary in G. Therefore, G is dual-Eulerian precisely when every face boundary in G has even length. For connected planar graphs, this condition is equivalent to G being bipartite, since a plane graph is bipartite if and only if all face cycles have even length. Hence, in the common setting of connected planar graphs with a fixed embedding, dual-Eulerian is equivalent to the graph being bipartite.

A note on embedding: the dual graph depends on the chosen planar embedding, so the dual-Eulerian property can vary with different embeddings for a given graph. In cases where the embedding is unique (for instance, for 3-connected planar graphs), the dual-Eulerian status is well-defined. The dual–Eulerian relationship is connected to the broader duality between Eulerian and bipartite graphs: a planar graph is Eulerian if and only if its dual is bipartite, and vice versa.

Applications and contexts include contrastive properties in planar graphs, network design, and topological graph theory, where understanding the parity of face lengths informs about bipartiteness and dual structures.