Dual Circumference and Collinear Sets

DOI10.4230/LIPICS.SOCG.2019.29MaRDI QIDQ6309406arXivFDO

Authors Vida Dujmović, Pat Morin

Publication date 8 November 2018

Published in arXiv

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2019.29

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

arXiv classification

math.CO

Abstract: We show that, if a $n$-vertex triangulation $T$ of maximum degree $Delta$ has a dual that contains a cycle of length $ell$, then $T$ has a non-crossing straight-line drawing in which some emph{collinear set} of $Omega(ell/Delt{a}^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}/Delt{a}^4)$. Very recently, Dujmovi'c et. al. (SODA 2019) showed that, if $S$ is a collinear set in a triangulation $T$ then, for any point set $Xsubsetmathbb{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.

This page was built for publication: Dual Circumference and Collinear Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6309406)