Veröffentlichung

Titel:
Recognizing Planar Laman Graphs
AutorInnen:
Jonathan Rollin
Lena Schlipf
André Schulz
Kategorie:
Workshopbeiträge
erschienen in:
Proceedings of the 35th European Workshop on Computational Geometry (EuroCG’19)
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 another one with running time O(n log^3 n) based on latest 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 SQR{n log n})

Download:
EuroCG
Lena Schlipf | 21.10.2021