Drawing disconnected graphs on surfaces
Status Open · unsolvedmath.comLLM status Open unverified
Top Open Problems Not reported cataloguedOpenOpenStatement
Definitions and mathematical statement
Let $G_1,G_2$ be finite graphs with disjoint vertex sets and no edge between them, and let $G=G_1\mathbin{\dot\cup}G_2$. Let $\Sigma$ be a connected closed surface. A drawing places vertices at distinct points and represents each edge by a simple arc between its endpoints. Edge interiors avoid vertices. Crossings are transverse intersections of edge interiors; there are finitely many, no three edge interiors meet at one point, and no tangencies or overlapping arc segments are allowed.Use good drawings: adjacent edges do not cross and two independent edges cross at most once. Count each crossing point once. The surface crossing number $\operatorname{cr}_\Sigma(G)$ is the minimum number of crossings among such drawings, and a drawing attaining it is optimal. The number includes crossings between different components as well as crossings within one component.
The conjecture asks whether every optimal drawing of $G$ on $\Sigma$ has disjoint images of $G_1$ and $G_2$. Equivalently, no edge of the first graph should cross an edge of the second in any drawing attaining $\operatorname{cr}_\Sigma(G)$.
The word every is part of the question: constructing one optimum without intercomponent crossings would be a weaker result. No surface region or handle is assigned to a component in advance, and neither $G_1$ nor $G_2$ need be planar or connected. Disjointness concerns their entire drawn images, while crossings among edges within an individual component remain permissible and may be unavoidable.
Short English statement
In every drawing with the minimum possible crossings on a surface, must two disjoint graph components have disjoint images?Sources
- S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3321 (OPG-322), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
- S2 Open Problem Garden, Drawing disconnected graphs on surfaces. Original problem and discussion. http://www.openproblemgarden.org/op/drawing_disconnected_graphs_on_surfaces.
Statement licence: CC-BY-4.0 · Source file
Contributions 0
No attempts yet. Significant partial results and substantial reductions are welcome. Contribute an attempt.