Crossing-critical graphs: those nonplanar graphs, whose crossing number drops down with every edge deletion

Definition. A graph G is k-crossing-critical if cr(G)>=k but cr(G-e)<k for all edges e of G.

Importance: Crossing-critical graphs capture structural properties of high crossing number. Precisely, every graph of crossing number k must contain a k-crossing-critical subgraph.

Basic examples

• Say, complete and complete bipartite graphs are crossing-critical. In general, every nonplanar edge-transitive graph is crossing-critical since some edge is crossed in an optimal drawing and the same drop in the crossing number can be observed on each of the equivalent edges.

• For a fixed k>1, there exist infinite k-crossing-critical families, and hence there is no simple characterization. Two basic approaches to crossing-critical consructions can be illustrated with the following:

Kochol's family (1987):  ...followed by many other similarly "twisted" constructions, and "planar tile" constructions

                                                         

 

And a crossed-fence example (2001): ...a rather exceptional non-twisted construction giving new rich families

                                            

The crossing number of a k-crossing-critical graph is indeed bounded

• R. Bruce Richter, Carsten Thomassen: Minimal Graphs with Crossing Number at Least k. J. Comb. Theory, Ser. B 58(2): 217-224 (1993)

• Can one come with a better bound for cr(G) than above? Still open, but hoping for k+O(sqrt(k)) ...
  

Average degree of critical graphs

• Gelasio Salazar: Infinite families of crossing-critical graphs with given average degree. Discrete Mathematics 271(1-3): 343-350 (2003)

In their paper on minimal graphs with crossing number at least k (or, equivalently, k-crossing-critical graphs) (J. Combin. Theory Ser. B 58 (2) (1993) 217–224) Richter and Thomassen described a construction of an infinite family of 4-regular 3-crossing-critical graphs. They also showed that no infinite family of 6-regular k-crossing-critical graphs exists. In this paper we generalize the Richter and Thomassen construction, and prove the following result: for each rational number q[4,6) there is an infinite family of graphs that are k-crossing-critical for the same integer k, each of which has average degree q. Moreover, we show that for each rational number q[4,6) this statement holds for infinitely many values of k.

 

• Benny Pinontoan, R. Bruce Richter. Crossing numbers of sequences of graphs II: Planar tiles. J Graph Theory 42: 332–341, 2003.

We describe a method of creating an infinite family of crossing-critical graphs from a single small planar map, the tile, by gluing together many copies of the tile together in a circular fashion. This method yields all known infinite families of k-crossing-critical graphs. Furthermore, the method yields new infinite families, which extend from (4,6) to (3.5,6) the interval of rationals r for which there is, for some k, an infinite sequence of k-crossing-critical graphs all having average degree r.

• Drago Bokal: Infinite families of crossing-critical graphs with prescribed average degree and crossing number. Journal of Graph Theory 65(2): 139-162 (2010). 

Abstract. Širáň constructed infinite families of k-crossing-critical graphs for every k⩾3 and Kochol constructed such families of simple graphs for every k⩾2. Richter and Thomassen argued that, for any given k⩾1 and r⩾6, there are only finitely many simple k-crossing-critical graphs with minimum degree r. Salazar observed that the same argument implies such a conclusion for simple k-crossing-critical graphs of prescribed average degree r>6. He established the existence of infinite families of simple k-crossing-critical graphs with any prescribed rational average degree r∈[4, 6) for infinitely many k and asked about their existence for r∈(3, 4). The question was partially settled by Pinontoan and Richter, who answered it positively for .

The present contribution uses two new constructions of crossing-critical simple graphs along with the one developed by Pinontoan and Richter to unify these results and to answer Salazar's question by the following statement: there exist infinite families of simple k-crossing-critical graphs with any prescribed average degree r∈(3, 6), for any k greater than some lower bound N_r. Moreover, a universal lower bound N_I on k applies for rational numbers in any closed interval I⊂(3, 6).

A critical tile with degrees close to 3:

 

More interesting constructions  

Zip-product construction by Bokal [many papers]:

This, among other uses, can give larger "combined" crossing critical grahs from critical pieces.

 

Another critical "belt" construction, giving always an almost-planar (i.e., with a planarizing edge) critical graph with great variability:  

 

• Petr Hliněný. The Electronic Journal of Combinatorics,  R102 of Volume 15(1), 2008.

 

 

    

Which particular vertex degrees occur infinitely often in crosing-critical families?

• A question raised by [Bokal] at the time when only degrees (2), 3,4,6 were known to be such...
• [Bokal et al] - degree 5 in a tile construction;
• [Hliněný] - any even degree (for suff. large, yet fixed k), by the above "belt" construction.