Infinite Families of Crossing-Critical Graphs with Prescribed Average Degree and Crossing Number

Siran 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 is an element of[4,6) for infinitely many k and asked about their existence for r is an element of(3,4). The question was partially settled by Pinontoan and Richter, who answered it positively for r is an element of(31/2, 4). 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 is an element of(3,6), for any k greater than some lower bound N(r). Moreover, a universal lower bound N(l) on k applies for rational numbers in any closed interval I subset of (3,6). (C) 2010 Wiley Periodicals. Inc. J Graph Theory 65: 139-162. 2010