Computer Science – Computational Geometry
Scientific paper
2008-09-23
Computer Science
Computational Geometry
Scientific paper
We define and study exact, efficient representations of realization spaces Euclidean Distance Constraint Systems (EDCS), which includes Linkages and Frameworks. Each representation corresponds to a choice of Cayley parameters and yields a different parametrized configuration space. Significantly, we give purely graph-theoretic, forbidden minor characterizations that capture (i) the class of graphs that always admit efficient configuration spaces and (ii) the possible choices of representation parameters that yield efficient configuration spaces for a given graph. In addition, our results are tight: we show counterexamples to obvious extensions. This is the first step in a systematic and graded program of combinatorial characterizations of efficient configuration spaces. We discuss several future theoretical and applied research directions. Some of our proofs employ an unusual interplay of (a) classical analytic results related to positive semi-definiteness of Euclidean distance matrices, with (b) recent forbidden minor characterizations and algorithms related to the notion of d-realizability of EDCS. We further introduce a novel type of restricted edge contraction or reduction to a graph minor, a "trick" that we anticipate will be useful in other situations.
Gao Heping
Sitharam Meera
No associations
LandOfFree
Characterizing graphs with convex and connected configuration spaces 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 Characterizing graphs with convex and connected configuration spaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Characterizing graphs with convex and connected configuration spaces will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-327319