We show that, if an n-vertex triangulation T of maximum degree ∆ has a dual that contains a cycle of length ℓ, then T has a non-crossing straight-line drawing in which some set, called a collinear set, of Ω(ℓ/∆4) vertices lie on a line. Using the current lower bounds on the length of longest cycles in 3-regular 3-connected graphs, this implies that every n-vertex planar graph of maximum degree ∆ has a collinear set of size Ω(n0.8/∆4). Very recently, Dujmović et al. (SODA 2019) showed that, if S is a collinear set in a triangulation T then, for any point set X ⊂ R2 with |X| = |S|, T has a non-crossing straight-line drawing in which the vertices of S are drawn on the points in X. Because of this, collinear sets have numerous applications in graph drawing and related areas.

Collinear sets, Column planarity, Partial simultaneous geometric drawings, Planar graphs, Universal point subsets, Untangling
35th International Symposium on Computational Geometry, SoCG 2019
School of Computer Science

Dujmović, V, & Morin, P. (2019). Dual circumference and collinear sets. In Leibniz International Proceedings in Informatics, LIPIcs. doi:10.4230/LIPIcs.SoCG.2019.29