The crossing number of a graph @math is the least number of crossings over all possible drawings of @math . We present a structural characterization of graphs with crossing number one.
A great deal of attention has been given to 2-crossing-critical graphs @cite_3 @cite_11 @cite_13 @cite_8 @cite_6 @cite_4 @cite_12 . For a positive integer @math , the @math on @math vertices, is the graph obtained from a @math -cycle by joining vertices with distance @math in the cycle. Bokal, Opporowski, Richter and Salazar @cite_12 characterized all 3-connected 2-crossing-critical graphs that contains a @math as a minor and all the ones not containing a @math as a minor. They also showed how to obtain all the not 3-connected 2-crossing-critical graphs from the 3-connected ones, and showed that there exists only finitely many 3-connected 2-crossing-critical graphs with no @math minor. It remains to characterize or enumerate all the 3-connected 2-crossing-critical graphs with a @math but no @math as a minor. We hope this work can help determine these remaining @math -crossing-critical graphs.
@cite_4 @cite_8 @cite_6 @cite_3 @cite_13 @cite_12 @cite_11
2507315201 2126687412 2112497773 2056837081
It is very well-known that there are precisely two minimal non-planar graphs: K 5 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 Mobius Ladder V 10 ; (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 10 ; and (iv) determine all the 3-connected 2-crossing-critical graphs that do not contain a subdivision of V 8 . We prove that, for every positive integer k, there is an integer N such that every 4-connected non-planar graph with at least N vertices has a minor isomorphic to K"4","k, the graph obtained from a cycle of length 2k+1 by adding an edge joining every pair of vertices at distance exactly k, or the graph obtained from a cycle of length k by adding two vertices adjacent to each other and to every vertex on the cycle. We also prove a version of this for subdivisions rather than minors, and relax the connectivity to allow 3-cuts with one side planar and of bounded size. We deduce that for every integer k there are only finitely many 3-connected 2-crossing-critical graphs with no subdivision isomorphic to the graph obtained from a cycle of length 2k by joining all pairs of diagonally opposite vertices. A graph is crossing-critical if deleting any edge decreases its crossing number on the plane. It is proved that, for any n >= 3, there is an infinite family of 3-connected crossing-critical graphs with crossing number n. Abstract A graph is crossing-critical if deleting any edge decreases its crossing number on the plane. For any n ⩾ 2 we present a construction of an infinite family of 3-connected crossing-critical graphs with crossing number n .