Characterizing 2-crossing-critical graphs

2013/12/13 by Drago Bokal, Bokal, Drago, Bogdan Oporowski +5 · 1 citation
Mathematics · #05C10 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C10

paper · pdf · doi:10.48550/arxiv.1312.3712

176 pages, 28 figures

arxiv created 2013/12/13 · arxiv updated 2013/12/16

Abstract

It is very well-known that there are precisely two minimal non-planar graphs: K₅ and K_3,3 (degree 2 vertices being irrelevant in this context). In the language of crossing numbers, these are the only 1-crossing-critical graphs: they each have crossing number at least one, and every proper subgraph has crossing number less than one. In 1987, Kochol exhibited an infinite family of 3-connected, simple 2-crossing-critical graphs. In this work, we: (i) determine all the 3-connected 2-crossing-critical graphs that contain a subdivision of the Möbius Ladder V₁₀; (ii) show how to obtain all the not 3-connected 2-crossing-critical graphs from the 3-connected ones; (iii) show that there are only finitely many 3-connected 2-crossing-critical graphs not containing a subdivision of V₁₀; and (iv) determine all the 3-connected 2-crossing-critical graphs that do not contain a subdivision of V₈.

Cited by

• Tanglegrams with a Unique 1-Crossing-Critical Subtanglegram have Tangle Crossing Number 1

Related

• Structure and generation of crossing-critical graphs
• Properties of Large 2-Crossing-Critical Graphs
• Counting Hamiltonian cycles in 2-tiled graphs
• A new infinite family of 4-regular crossing-critical graphs
• Infinite families of crossing-critical graphs with prescribed average degree and crossing number