Name
Abstract | ||
|---|---|---|
We prove that all planar Laman graphs (i.e. minimally generically rigid graphs with a non-crossing planar embedding) can be generated from a single edge by a sequence of vertex splits. It has been shown recently [6,12] that a graph has a pointed pseudo-triangular embedding if and only if it is a planar Laman graph. Due to this connection, our result gives a new tool for attacking problems in the area of pseudo-triangulations and related geometric objects. One advantage of vertex splitting over alternate constructions, such as edge-splitting, is that vertex splitting is geometrically more local. We also give new inductive constructions for duals of planar Laman graphs and for planar generically rigid graphs containing a unique rigidity circuit. Our constructions can be found in O(n(3)) time, which matches the best running time bound that has been achieved for other inductive contructions. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-30140-0_28 | ALGORITHMS ESA 2004, PROCEEDINGS |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Embedding,Laman graph,Vertex (geometry),Vertex (graph theory),Planar straight-line graph,Chordal graph,Triangulation (social science),Mathematics,Planar graph | Conference | 3221 |
ISSN | Citations | PageRank |
0302-9743 | 2 | 0.38 |
References | Authors | |
8 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zsolt Fekete | 1 | 24 | 6.37 |
| Tibor Jordán | 2 | 713 | 78.34 |
| Walter Whiteley | 3 | 450 | 32.34 |