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.

, , , , ,
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