Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.79
URN: urn:nbn:de:0030-drops-112001
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11200/
Rollin, Jonathan ; Schlipf, Lena ; Schulz, André
Recognizing Planar Laman Graphs
| pdf-format: |
|
Abstract
Laman graphs are the minimally rigid graphs in the plane. We present two algorithms for recognizing planar Laman graphs. A simple algorithm with running time O(n^(3/2)) and a more complicated algorithm with running time O(n log^3 n) based on involved planar network flow algorithms. Both improve upon the previously fastest algorithm for general graphs by Gabow and Westermann [Algorithmica, 7(5-6):465 - 497, 1992] with running time O(n sqrt{n log n}).To solve this problem we introduce two algorithms (with the running times stated above) that check whether for a directed planar graph G, disjoint sets S, T subseteq V(G), and a fixed k the following connectivity condition holds: for each vertex s in S there are k directed paths from s to T pairwise having only vertex s in common. This variant of connectivity seems interesting on its own.
BibTeX - Entry
@InProceedings{rollin_et_al:LIPIcs:2019:11200,
author = {Jonathan Rollin and Lena Schlipf and Andr{\'e} Schulz},
title = {{Recognizing Planar Laman Graphs}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {79:1--79:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-124-5},
ISSN = {1868-8969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11200},
URN = {urn:nbn:de:0030-drops-112001},
doi = {10.4230/LIPIcs.ESA.2019.79},
annote = {Keywords: planar graphs, Laman graphs, network flow, connectivity}
}
| Keywords: | planar graphs, Laman graphs, network flow, connectivity | |
| Seminar: | 27th Annual European Symposium on Algorithms (ESA 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 06.09.2019 |
