Computer Science – Computational Geometry
Scientific paper
2010-10-19
Computer Science
Computational Geometry
Scientific paper
Maxwell's condition states that the edges of a graph are independent in its $d$-dimensional generic rigidity matroid only if $(a)$ the number of edges does not exceed $d|V| - {d+1\choose 2}$, and $(b)$ this holds for every induced subgraph. We call such graphs {\em Maxwell-independent} in $d$ dimensions. Laman's theorem shows that the converse holds in 2D. While the converse is false in 3D, we answer the following questions in the affirmative. The first question was posed by Tib\'or Jord\'an at the 2008 rigidity workshop at BIRS \cite{bib:birs}. Question 1: Does {\it every} maximal, Maxwell-independent set of a graph have size at least the rank? Question 2: Is there a better and tractable combinatorial rank upper bound (than the number of edges) for Maxwell-independent graphs? We give affirmative answers to both questions and construct a set of edges that meets the latter upper bound and contains a maximal (true) independent set. We extend these bounds to special classes of non-Maxwell-independent graphs. As one consequence, the answers also give simpler proofs of correctness for existing algorithms that give rank bounds.
Cheng Jialong
Sitharam Meera
No associations
LandOfFree
Maxwell-independence: a new rank estimate for 3D rigidity matroids does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Maxwell-independence: a new rank estimate for 3D rigidity matroids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maxwell-independence: a new rank estimate for 3D rigidity matroids will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-716755