Towards an optimal algorithm for recognizing Laman graphs

Ovidiu Daescu*, Anastasia Kurdia

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A graph G with n vertices and m edges is a Laman graph, or equivalently a generically minimally rigid 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 vertices, decide if it is Laman. We present an algorithm that recognizes Laman graphs in 0(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 thatT st(n) is O(n 3/2√log n).

Original languageEnglish (US)
Title of host publicationProceedings of the 42nd Annual Hawaii International Conference on System Sciences, HICSS
DOIs
StatePublished - 2009
Event42nd Annual Hawaii International Conference on System Sciences, HICSS - Waikoloa, HI, United States
Duration: Jan 5 2009Jan 9 2009

Publication series

NameProceedings of the 42nd Annual Hawaii International Conference on System Sciences, HICSS

Conference

Conference42nd Annual Hawaii International Conference on System Sciences, HICSS
Country/TerritoryUnited States
CityWaikoloa, HI
Period1/5/091/9/09

ASJC Scopus subject areas

  • Computer Science Applications
  • Information Systems

Fingerprint

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

Cite this