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
2112497773 2090034967 193336535 2056837081 2507315201 2126687412
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. It is proved that every cubic graph with crossing number at least two contains a subdivision of one of eight graphs. A spelling net for a phrase consists of the multigraph whose points are labelled with the set of distinct letters in the phrase and whose lines lie on the Eulerian path obtained in "spelling out" the phrase between the (lettered) points. Spelling nets can also use phonemes or words as labels. An eodermdrome is a non-planar spelling net. Thus, the study of structural properties of eodermdromes is the study of non-planar Eulerian multigraphs. 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 . 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.