## 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 ver- tices, decide if it is Laman. We present an algorithm that recognizes Laman graphs in O(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 that 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 that T _{st}(n) is O(n ^{3/2} log n).

Original language | English (US) |
---|---|

Pages (from-to) | 219-232 |

Number of pages | 14 |

Journal | Journal of Graph Algorithms and Applications |

Volume | 13 |

Issue number | 2 |

DOIs | |

State | Published - 2009 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science
- Computer Science Applications
- Geometry and Topology
- Computational Theory and Mathematics