As I said in my previous post my two SoCG papers both involved trying and failing to prove something else, and writing down what I could prove instead. For the one that appears today, “Cubic planar graphs that cannot be drawn on few lines” (arXiv:1903.05256), that something else was Open Problem 16.14 of my book, which can be rephrased as: does there exist a family of planar graphs that cannot be drawn planarly with all vertices on a constant number of convex curves?

Instead I expand on something that was already known, the existence of planar graphs that cannot be drawn with all vertices on a constant number of lines.

There were two previously known methods for constructing such graphs:

  • Use a planar 3-tree. This is a planar graph formed by recursively subdividing triangles into three smaller triangles. If the vertices are drawn on some family of lines, the line through the subdivision point must miss one of the three smaller triangles, so by induction you can be forced to use a non-constant number of lines. But the bound you get is only logarithmic.1

Planar 3-tree

  • Use a maximal planar graph whose dual graph has no long paths. In a maximal planar graph, any line through many vertices can be translated into a path through many dual vertices. So if there is no long dual path there must be many lines. This gives a polynomial lower bound on the number of lines, but with a tiny exponent.2

The new paper finds a third method:

  • Use a graph that has many disjoint collections of many nested cycles. Drawing a big set of nested cycles on a small number of lines necessarily uses up one of the crossing points of the lines. So if there are more nests than crossing points, one of them will have to use many lines.

Graph with many disjoint collections of many nested cycles

This leads to stronger polynomial bounds, but also (more importantly I think) wider families of planar graphs that need non-constant numbers of lines. For instance, it works for series-parallel graphs of maximum degree three, which are far from being maximal planar. And even though every tree can be drawn with its vertices on two lines, adding a single vertex to a tree can produce a graph that requires a non-constant number of lines.

Tree plus one vertex requiring a non-constant number of lines

  1. Forbidden Configurations in Discrete Geometry, Theorem 16.13. ↩

  2. Ravsky, Alexander, and Verbitsky, Oleg (2011), “On collinear sets in straight-line drawings”, 37th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2011), LNCS 6986, Springer, pp. 295–306; Chaplick, Steven, Fleszar, Krzysztof, Lipp, Fabian, Verbitsky, Oleg, and Wolff, Alexander (2016), “Drawing graphs on few lines and few planes”, 24th Int. Symp. Graph Drawing and Network Visualization (GD 2016), LNCS 9801, Springer, pp. 166–180. ↩

(Discuss on Mastodon)