New almost-planar crossing-critical graph families
Petr Hliněný · 2007
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 $5$ in crossing-critical graphs remains open. Furthermore, our 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 $\big[4,6-\frac8{k+1}\big)$.