Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00185
Towards an optimal algorithm for recognizing Laman graphs
Vol. 13, no. 2, pp. 219-232, 2009. Concise paper.
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 vertices, decide if it is Laman. We present an algorithm that
recognizes Laman graphs in O(Tst(n)+n logn) time, where
Tst(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 Tst(n) is
O(n3/2√{logn}).
|
Submitted: April 2008.
Reviewed: December 2008.
Revised: January 2009.
Reviewed: May 2009.
Revised: May 2009.
Accepted: July 2009.
Final: July 2009.
Published: July 2009.
Communicated by
Ioannis G. Tollis
|
Journal Supporters
|