2026-07-24T01:59:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10436 2024-03-06T10:45:59Z ddc:004 open_access

Cubic Planar Graphs That Cannot Be Drawn On Few Lines Eppstein, David graph drawing universal point sets collinearity For every integer l, we construct a cubic 3-vertex-connected planar bipartite graph G with O(l^3) vertices such that there is no planar straight-line drawing of G whose vertices all lie on l 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Eppstein 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.32 urn:nbn:de:0030-drops-104363 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.32 eng https://creativecommons.org/licenses/by/3.0/legalcode