It is NP-hard to decide whether a planar graph can be drawn with all vertices on two straight lines, and any graph drawable on two planes has at most 5n minus 19 edges.
Cubic Planar Graphs that cannot be Drawn on few Lines
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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.
fields
cs.CG 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Line and Plane Cover Numbers Revisited
It is NP-hard to decide whether a planar graph can be drawn with all vertices on two straight lines, and any graph drawable on two planes has at most 5n minus 19 edges.