Cubic Planar Graphs that cannot be Drawn on few Lines

Abstract

For every integer $\ell$, we construct a cubic 3-vertex-connected planar bipartite graph $G$ with $O({\ell }^3)$ vertices such that there is no planar straight-line drawing of $G$ whose vertices all lie on $\ell$ lines. This strengthens previous results on graphs that cannot be drawn on few lines, which constructed significantly larger maximal planar graphs. We also find apex-trees and cubic bipartite series-parallel graphs that cannot be drawn on a bounded number of lines.

15 pages, 10 figures. To appear in Proceedings of the 35th International Symposium on Computational Geometry (SoCG 2019)

References in corpus (1)

• Minor-closed graph classes with bounded layered pathwidth