New infinite families of almost-planar crossing-critical graphs (Q1010829)

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 \(\leq2k-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+\frac{1}{5},6-\frac{8}{k+1})\).