Geodesic
Towards an optimal algorithm for recognizing Laman graphs
Journal of Graph Algorithms and Applications, Tome 13 (2009) no. 2, pp. 219-232.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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}).
DOI : 10.7155/jgaa.00185
Keywords: rigidity, Laman graph, verification, red-black hierarchy 
@article{JGAA_2009_13_2_a8,
     author = {Ovidiu Daescu and Anastasia Kurdia},
     title = {Towards an optimal algorithm for recognizing {Laman} graphs},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {219--232},
     publisher = {mathdoc},
     volume = {13},
     number = {2},
     year = {2009},
     doi = {10.7155/jgaa.00185},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00185/}
}
TY  - JOUR
AU  - Ovidiu Daescu
AU  - Anastasia Kurdia
TI  - Towards an optimal algorithm for recognizing Laman graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2009
SP  - 219
EP  - 232
VL  - 13
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00185/
DO  - 10.7155/jgaa.00185
LA  - en
ID  - JGAA_2009_13_2_a8
ER  - 
%0 Journal Article
%A Ovidiu Daescu
%A Anastasia Kurdia
%T Towards an optimal algorithm for recognizing Laman graphs
%J Journal of Graph Algorithms and Applications
%D 2009
%P 219-232
%V 13
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00185/
%R 10.7155/jgaa.00185
%G en
%F JGAA_2009_13_2_a8
Ovidiu Daescu; Anastasia Kurdia. Towards an optimal algorithm for recognizing Laman graphs. Journal of Graph Algorithms and Applications, Tome 13 (2009) no. 2, pp. 219-232. doi : 10.7155/jgaa.00185. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00185/

Cité par Sources :