Cycle Double Cover - Circular Embedding Conjecture

Circular Embedding Conjecture

If a graph has a cycle double cover, the cycles of the cover can be used to form the 2-cells of a graph embedding onto a two-dimensional cell complex. In the case of a cubic graph, this complex always forms a manifold. The graph is said to be circularly embedded onto the manifold, in that every face of the embedding is a simple cycle in the graph. However, a cycle double cover of a graph with degree greater than three may not correspond to an embedding on a manifold: the cell complex formed by the cycles of the cover may have non-manifold topology at its vertices. The circular embedding conjecture or strong embedding conjecture states that every biconnected graph has a circular embedding onto a manifold. If so, the graph also has a cycle double cover, formed by the faces of the embedding.

For cubic graphs, biconnectivity and bridgelessness are equivalent. Therefore, the circular embedding conjecture is clearly at least as strong as the cycle double cover conjecture. However, it turns out to be no stronger. If the vertices of a graph G are expanded to form a cubic graph, which is then circularly embedded, and the expansions are undone by contracting the added edges, the result will be a circular embedding of G itself. Therefore, if the cycle double cover conjecture is true, every biconnected graph has a circular embedding. That is, the cycle double cover conjecture is equivalent to the circular embedding conjecture, even though a cycle double cover and a circular embedding are not always the same thing.

If a circular embedding exists, it might not be on a surface of minimal genus: Nguyen Huy Xuong described a biconnected toroidal graph none of whose circular embeddings lie on a torus.