TY - GEN

T1 - Towards an optimal algorithm for recognizing Laman graphs

AU - Daescu, Ovidiu

AU - Kurdia, Anastasia

PY - 2009

Y1 - 2009

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=78650760785&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78650760785&partnerID=8YFLogxK

U2 - 10.1109/HICSS.2009.470

DO - 10.1109/HICSS.2009.470

M3 - Conference contribution

AN - SCOPUS:78650760785

SN - 9780769534503

T3 - Proceedings of the 42nd Annual Hawaii International Conference on System Sciences, HICSS

BT - Proceedings of the 42nd Annual Hawaii International Conference on System Sciences, HICSS

T2 - 42nd Annual Hawaii International Conference on System Sciences, HICSS

Y2 - 5 January 2009 through 9 January 2009

ER -