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