×

On characterizations of rigid graphs in the plane using spanning trees. (English) Zbl 1221.05038

Summary: We study characterizations of generic rigid graphs and generic circuits in the plane using only few decompositions into spanning trees. Generic rigid graphs in the plane can be characterized by spanning tree decompositions. A graph \(G\) with \(n\) vertices and \(2n - 3\) edges is generic rigid in the plane if and only if doubling any edge results in a graph which is the union of two spanning trees. This requires \(2n - 3\) decompositions into spanning trees. We show that \(n - 2\) decompositions suffice: only edges of \(G - T\) can be doubled where \(T\) is a spanning tree of \(G\).
A recent result on tensegrity frameworks by A. Recski [“Combinatorial conditions for the rigidity of tensegrity frameworks,” Bolyai Society Mathematical Studies 17, 163-177 (2008; Zbl 1152.52010)] implies a characterization of generic circuits in the plane. A graph \(G\) with \(n\) vertices and \(2n - 2\) edges is a generic circuit in the plane if and only if replacing any edge of \(G\) by any (possibly new) edge results in a graph which is the union of two spanning trees. This requires \((2n-2)(\binom{n}{2} - 1)+1\) decompositions into spanning trees. We show that \(2n - 2\) decompositions suffice. Let \(e_1,e_2,\ldots,e_{2n-2}\) be any circular order of edges of \(G\) (i.e., \(e_0 = e_{2n-2}\)). The graph \(G\) is a generic circuit in the plane if and only if \(G + e_i - e_{i-1}\) is the union of two spanning trees for any \(i = 1,2, \ldots, 2n-2\). Furthermore, we show that only \(n\) decompositions into spanning trees suffice.

MSC:

05C05 Trees
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
52C25 Rigidity and flexibility of structures (aspects of discrete geometry)

Citations:

Zbl 1152.52010
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Crapo, H.: On the generic rigidity of structures in the plane. Technical Report, Inst. nat. rech. en informatique et automatique (INRIA) 1143 (1989)
[2] Edmonds, J.: Minimum partition of a matroid into independent sets. Research of the NBS, 69, 67–72 (1965) · Zbl 0192.09101
[3] Jordán, T., Recski, A., Szabadka, Z.: Rigid tensegrity labellings of graphs. Technical Report TR-2007-08, Egerváry Research Group, Budapest (2007) · Zbl 1226.05216
[4] Laman, G.: On graphs and rigidity of plane skeletal structures. J. Eng. Math., 4, 331–340 (1970) · Zbl 0213.51903
[5] Lovász, L., Yemini, Y.: On generic rigidity in the plane. SIAM J. Algebr. Disc. Meth., 3, 91–98 (1982) · Zbl 0497.05025
[6] Recski, A.: A network theory approach to the rigidity of skeletal structures, Part II. Laman’s theorem and topological formulae. Disc. Appl. Math., 8, 63–68 (1984) · Zbl 0537.51028
[7] Recski, A.: Combinatorial conditions for the rigidity of tensegrity frameworks. The Kyoto International Conference on Computational Geometry and Graph Theory (2007) · Zbl 1152.52010
[8] Whiteley, W.: Some matroids from discrete applied geometry. In: Bonin, J. E., Oxley, J. G. Servatius, B. (eds). Contemporary Mathematics, volume 197, pp. 171–311. American Mathematical Society, Seattle, WA, 1997 · Zbl 0860.05018
[9] Whiteley, W.: Rigidity and scene analysis. In: Goodman, J.E., O’Rourke, J. (eds). Handbook of Discrete and Computational Geometry, chapter 60, pp. 1327–1354. CRC Press LLC, Boca Raton, FL (2004)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.