Veröffentlichung

Titel:

Recognizing Planar Laman Graphs

AutorInnen:

Jonathan Rollin
Lena Schlipf
André Schulz

Kategorie:

Konferenzbandbeiträge

erschienen in:

Proceedings of the 27th Annual European Symposium on Algorithms (ESA'19), Seiten 79:1--79:12

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.

Download:

DROPS

BibTeX-Eintrag:

@InProceedings{ author = {Jonathan Rollin and Lena Schlipf and Andr{\'e} Schulz}, title = {Recognizing Planar Laman Graphs}, booktitle = {27th Annual European Symposium on Algorithms (ESA'19)}, pages = {79:1--79:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, year = {2019}, volume = {144}, doi = {10.4230/LIPIcs.ESA.2019.79}, }