The circular embedding conjecture
OPG_2_connected_circular_surface_embedding
Source: Open Problem Garden: the_circular_embedding_conjecture
Status partial high confidence
The circular embedding conjecture (equivalently, the strong embedding conjecture) is now settled for cubic graphs and remains open for general 2-connected graphs. The cubic case follows from the July 2026 proof of the cycle double cover conjecture (OpenAI/GPT-5.6; exposition arXiv:2607.16356, Section 1) via the classical reduction in Jaeger's survey: for cubic graphs a cycle double cover and a closed 2-cell embedding are interchangeable. Earlier progress: Ellingham and Zha (2011) proved the orientable variant for 2-connected projective-planar cubic graphs, and Ghanbari and Sámal (2026) develop facial-diagram tools bounding singular edges in circular 2-cell embeddings. The general (non-cubic) case, and the orientable strengthening, are untouched by the new proof.
Cited literature (3)
-
The cycle double cover conjecture is now a theorem (proof announced by OpenAI in July 2026; Theorem 1 of this exposition). Since a cycle double cover of a cubic graph yields a strong (closed 2-cell) embedding -- the reduction recorded in Jaeger's survey -- the circular embedding conjecture now holds for all 2-connected cubic graphs. Section 1 states it explicitly: "Theorem 1 proves Conjecture 2 for cubic graphs". The conjecture remains open for general 2-connected graphs, and the embedding it produces need not be orientable.
-
Proves that every 2-connected projective-planar cubic graph has a closed 2-cell (circular) embedding in some orientable surface, and that every 2-edge-connected projective-planar graph has an orientable cycle double cover, establishing the oriented circular embedding conjecture for this graph class.
-
Introduces a facial-diagram framework for circular 2-cell embeddings of cubic graphs, studies an edge-twisting operation that transforms one 2-cell embedding into another, and derives bounds on the number of singular edges, providing new tools for attacking the circular embedding / cycle double cover conjecture.
Reviewer notes. Mohar (2009/2010, arXiv:0908.1933) showed that closed 2-cell embeddings may require surfaces of genus proportional to the order of the graph for some cubic graphs, disproving a minimum-genus folklore conjecture attributed to Tutte, but this does not disprove the circular embedding conjecture (which asks for existence on any surface). Ellingham and Zha (2015, arXiv:1501.06043) developed a partial-duality characterisation of closed 2-cell embeddings. A claim circulating in survey literature that 'any 2-connected graph without the Möbius 4-ladder as a minor has a closed 2-cell embedding' could not be traced to a verifiable source within the search budget. The ScienceDirect page for the Ellingham-Zha journal paper returned HTTP 403; the arXiv preprint was verified instead. 2026-09-06 update: the cycle double cover conjecture itself is now a theorem (OpenAI/GPT-5.6, July 2026; exposition arXiv:2607.16356). Because this conjecture implies CDC, the implication edge to opg:cycle_double_cover_conjecture in data/relations.json is now vacuous; the live content of this page is the non-cubic case, which the new proof does not reach (vertex splitting destroys the embedding).
Discussion
This conjecture implies the cycle double cover conjecture , since the list of cycles which bound faces covers each edge exactly twice. Let $ G $ be a cubic graph, let $ L $ be a list of cycles covering every edge of $ G $ exactly two times, and form a topological space by gluing a disc to each circuit in $ L $ . This space is a surface, and every face is bounded by a cycle. Thus, the circular embedding conjecture and the cycle double cover conjecture are equivalent for cubic graphs. For general graphs, this construction may fail since the neighborhood of a vertex may not be a disc (it could be a pinchpoint). A stronger variant of this conjecture asserts that it is possible to find an embedding as above with the added condition that the dual graph is 5-colorable. This variant implies The five cycle double cover conjecture since the circuits bounding faces of a given color class may be grouped into a cycle. Next we state a different strengthening which asserts that we may find an embedding as above into an orientable surface. Conjecture (The oriented circular embedding conjecture) Every 2-connected graph may be embedded in an orientable surface so that the boundary of each face is a circuit. If this conjecture is true, then the oriented cycle double cover conjecture (see cycle double cover ) is also true, since the list of circuits bounding faces all traversed in the clockwise direction cover each edge exactly once in each direction (since the surface is orientable, we may specify a global clockwise orientation). As was the case above, the oriented circular embedding conjecture is equivalent to the oriented cycle double cover conjecture for cubic graphs. Also as above, there is a strengthening of this conjecture which asserts that the graph may be embedded so that the dual graph is 5-colorable. If true, this would imply The orientable five cycle double cover conjecture.
Bibliography
-
[H]G. Haggard, Edmonds characterization of disc embeddings. Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), pp. 291--302. MathSciNet MathSciNet