2026-08-16T18:54:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11200 2024-03-06T10:47:41Z ddc:004 open_access

Recognizing Planar Laman Graphs Rollin, Jonathan Schlipf, Lena Schulz, André planar graphs Laman graphs network flow connectivity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jonathan Rollin and Lena Schlipf and André Schulz 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.79 urn:nbn:de:0030-drops-112001 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.79 eng https://creativecommons.org/licenses/by/3.0/legalcode