摘要：We show that, if an n-vertex triangulation T of maximum degree Delta has a dual that contains a cycle of length l, then T has a non-crossing straight-line drawing in which some set, called a collinear set, of Omega(l/Delta^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 Delta has a collinear set of size Omega(n^{0.8}/Delta^4). Very recently, Dujmovic et al. (SODA 2019) showed that, if S is a collinear set in a triangulation T then, for any point set X subset R^2 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.
