## New infinite families of almost-planar crossing-critical graphs

### Summary

Summary: 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 $\leq$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 + 1 , 6 - 8 .

05C10, 05C62

### Keywords/Phrases

crossing number, graph drawing, crossing-critical graph