New Infinite Families of Almost-Planar Crossing-Critical Graphs - Hliněný, Petr (The Electronic Journal of Combinatorics, 2008)
We show that, for all choices of integers k>2 and m, there are simple 3-connected k-crossing-critical graphs containing more than m vertices of each even degree ≤2k-2. This construction answers one half of a question raised by Bokal, while the other half asking analogously about vertices of odd degrees at least 7 in crossing-critical graphs remains open. Furthermore, our newly constructed graphs have several other interesting properties; for instance, they are almost planar and their average degree can attain any rational value in the interval [3+15,6-8k+1).