2026-08-16T16:35:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10433 2024-03-06T10:45:58Z ddc:004 open_access

Dual Circumference and Collinear Sets Dujmović, Vida Morin, Pat Planar graphs collinear sets untangling column planarity universal point subsets partial simultaneous geometric drawings 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, Dujmović 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vida Dujmović and Pat Morin 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.29 urn:nbn:de:0030-drops-104338 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.29 eng https://creativecommons.org/licenses/by/3.0/legalcode