REVIEW 1 cited by
Cubic Planar Graphs that cannot be Drawn on few Lines
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
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.
Forward citations
Cited by 1 Pith paper
-
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.
Discussion (0). Continue with ORCID to comment.