Structure and generation of crossing-critical graphs

2018/03/05 by Zdenĕk Dvořák, Dvořák, Zdeněk, Petr Hliněný +3
Computer Science · #05C10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1803.01931

openalex publication_date 2018/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For c=1 there are only two such graphs without degree-2 vertices, K₅ and K_3,3, but for any fixed c>1 there exist infinitely many c-crossing-critical graphs. It has been previously shown that c-crossing-critical graphs have bounded path-width and contain only a bounded number of internally disjoint paths between any two vertices. We expand on these results, providing a more detailed description of the structure of crossing-critical graphs. On the way towards this description, we prove a new structural characterisation of plane graphs of bounded path-width. Then we show that every c-crossing-critical graph can be obtained from a c-crossing-critical graph of bounded size by replicating bounded-size parts that already appear in narrow "bands" or "fans" in the graph. This also gives an algorithm to generate all the c-crossing-critical graphs of at most given order n in polynomial time per each generated graph.

Related

• Bounded maximum degree conjecture holds precisely for c-crossing-critical graphs with c ≤ 12
• Improvement on the crossing number of crossing-critical graphs
• Making a graph crossing-critical by multiplying its edges
• Properties of Large 2-Crossing-Critical Graphs
• A new infinite family of 4-regular crossing-critical graphs