Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2019.29
URN: urn:nbn:de:0030-drops-104338
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10433/
Dujmovic, Vida ; Morin, Pat
Dual Circumference and Collinear Sets
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{dujmovic_et_al:LIPIcs:2019:10433,
author = {Vida Dujmovic and Pat Morin},
title = {{Dual Circumference and Collinear Sets}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {29:1--29:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Gill Barequet and Yusu Wang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10433},
URN = {urn:nbn:de:0030-drops-104338},
doi = {10.4230/LIPIcs.SoCG.2019.29},
annote = {Keywords: Planar graphs, collinear sets, untangling, column planarity, universal point subsets, partial simultaneous geometric drawings}
}
| Keywords: | Planar graphs, collinear sets, untangling, column planarity, universal point subsets, partial simultaneous geometric drawings | |
| Seminar: | 35th International Symposium on Computational Geometry (SoCG 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 11.06.2019 |
