Improvement on the crossing number of crossing-critical graphs

2020/03/03 by Barát, János, Tóth, Géza
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2003.01477

Abstract

The crossing number of a graph G is the minimum number of edge crossings over all drawings of G in the plane. A graph G is k-crossing-critical if its crossing number is at least k, but if we remove any edge of G, its crossing number drops below k. There are examples of k-crossing-critical graphs that do not have drawings with exactly k crossings. Richter and Thomassen proved in 1993 that if G is k-crossing-critical, then its crossing number is at most 2.5k+16. We improve this bound to 2k+6√(k)+44.

Related

• New upper bounds for the crossing numbers of crossing-critical graphs
• A new infinite family of 4-regular crossing-critical graphs
• Structure and generation of crossing-critical graphs
• Making a graph crossing-critical by multiplying its edges
• Generalizations of the Crossing Lemma