Towards an optimal algorithm for recognizing Laman graphs

DOI10.7155/JGAA.00185MaRDI QIDQ3184612zbMATH OpenOpenAlexFDO

Authors Ovidiu Daescu, Anastasia Kurdia

Publication date 21 October 2009

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/0801.2404

zbMATH Keywords

rigid graphrigidity theory

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Abstract: Laman graphs are fundamental to rigidity theory. A graph G with n vertices and m edges is a generic minimally rigid graph (Laman graph), if m=2n-3 and every induced subset of k vertices spans at most 2k-3 edges. We consider the verification problem: Given a graph G with n vertices, decide if it is Laman. We present an algorithm that takes O(T(n)+n log n) time, where T(n) is the best time to extract two edge disjoint spanning trees from G or decide no such trees exist. Our algorithm exploits a known construction called red-black hierarchy (RBH), that is a certificate for Laman graphs. First, we show how to verify if G admits an RBH and argue this is enough to conclude whether G is Laman or not. Second, we show how to construct the RBH using a two steps procedure that is simple and easy to implement. Finally, we point out some difficulties in using red-black hierarchies to compute a Henneberg construction, which seem to imply super-quadratic time algorithms when used for embedding a planar Laman graph as a pointed pseudo-triangulation.

Recommendations

• Certifying and constructing minimally rigid graphs in the plane
• Augmenting the rigidity of a graph in \(\mathbb R^{2}\)
• An efficient algorithm for testing the generic rigidity of graphs in the plane
• A Henneberg-based algorithm for generating tree-decomposable minimally rigid graphs
• Efficient algorithms for the d-dimensional rigidity matroid of sparse graphs

Cited in

(9)

• An efficient algorithm for testing the generic rigidity of graphs in the plane
• scientific article; zbMATH DE number 1547155 (Why is no real title available?)
• The number of realizations of a Laman graph
• A Henneberg-based algorithm for generating tree-decomposable minimally rigid graphs
• Recognizing planar Laman graphs
• Certifying and constructing minimally rigid graphs in the plane
• Algorithms – ESA 2004
• Combinatorial and geometric properties of planar Laman graphs
• Augmenting the rigidity of a graph in \(\mathbb R^{2}\)

This page was built for publication: Towards an optimal algorithm for recognizing Laman graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3184612)