Hlineny, Petr

New infinite families of almost-planar crossing-critical graphs

Electron. J. Comb. 15(1), Research Paper R102, 12 p. (2008)


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 .

Mathematics Subject Classification

05C10, 05C62


crossing number, graph drawing, crossing-critical graph