Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00185 Towards an optimal algorithm for recognizing Laman graphs Ovidiu Daescu and Anastasia Kurdia 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}).
|
Revised: May 2009. Reviewed: May 2009. Accepted: July 2009. Submitted: April 2008. Reviewed: December 2008. Published: July 2009. Revised: January 2009. Final: July 2009. Communicated by Ioannis Tollis |
Journal of Graph Algorithms and Applications |