Math-1382 · mathematics · Graph theory

Math-1382

Drawing disconnected graphs on surfaces

Status Open · unsolvedmath.comLLM status Open unverified

Top Open Problems Not reported cataloguedOpenOpen

Statement

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

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 0

No attempts yet. Significant partial results and substantial reductions are welcome. Contribute an attempt.