Towards an optimal algorithm for recognizing Laman graphs

Ovidiu Daescu*, Anastasia Kurdia

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

A graph G with n vertices and m edges is a generically minimally rigid graph (Laman graph), if m = 2n-3 and every induced subset of k vertices spans at most 2k - 3 edges. Laman graphs play a fundamental role in rigidity theory. We discuss the Verification problem: Given a graph G with n ver- tices, decide if it is Laman. We present an algorithm that recognizes Laman graphs in O(T st(n) + n log n) time, where T st(n) is the best time to extract two edge disjoint spanning trees from a graph with n vertices and 2n - 2 edges, or decide no such trees exist. So far, it is known that T st(n) is the best time to extract two edge disjoint spanning trees from a graph with n vertices and 2n - 2 edges, or decide no such trees exist. So far, it is known that T st(n) is O(n 3/2 log n).

Original languageEnglish (US)
Pages (from-to)219-232
Number of pages14
JournalJournal of Graph Algorithms and Applications
Volume13
Issue number2
DOIs
StatePublished - 2009

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science
  • Computer Science Applications
  • Geometry and Topology
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Towards an optimal algorithm for recognizing Laman graphs'. Together they form a unique fingerprint.

Cite this