The potential crossing pair characterization of graphs with crossing number at least 2

Let GG be a non-planar graph. A pair of edges {e,f}\{e,f\} of GG is a potential crossing pair if, for every Kuratowski subgraph HH of GG, ee and ff form a crossing pair of HH. The crossing number of GG, denoted by cr(G)\operatorname{cr}(G), is the minimum number of crossings in a drawing of GG in the plane.

Potential crossing pair conjecture. The graph GG has crossing number at least 22 if and only if it does not have a potential crossing pair.

This question arises from the characterization of crossing pairs in the preceding theorem: a potential crossing pair that is not separated by cycles is a crossing pair. Thus, any potential crossing pair in a graph with crossing number at least 22 would necessarily be separated by cycles. The source does not provide a resolution of this characterization.

Sources & referencesView supporting material

Primary source

André C. Silva, Alan Arroyo, R. Bruce Richter and Orlando Lee, “Graphs with at most one crossing”, arXiv:1901.09955 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.