Cubic Planar Graphs that cannot be Drawn on few Lines

03/12/2019
by   David Eppstein, et al.
0

For every integer ℓ, we construct a cubic 3-vertex-connected planar bipartite graph G with O(ℓ^3) vertices such that there is no planar straight-line drawing of G whose vertices all lie on ℓ 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset