Cubic planar graphs that cannot be drawn on few lines.
D. Eppstein.
arXiv:1903.05256.
Proc. 35th Int. Symp. on Computational Geometry, Portland,
Oregon, June 2019.
Leibniz International
Proceedings in Informatics (LIPIcs) 129, 2019, pp. 32:1–32:15, doi:10.4230/LIPIcs.SoCG.2019.32.
J. Computational Geometry 12 (1): 178–197, 2021, doi:10.20382/v12i1a8.
We construct planar graphs whose straight drawings require a large number of lines (at least the cube root of the number of vertices) to cover all vertices. We also find series-parallel graphs and apex-trees that require a non-constant number of lines.
(SoCG'19 slides – Blog post: Planar graphs needing many lines)
