Cayley Configuration Spaces of 1-dof Tree-decomposable Linkages, Part II: Combinatorial Characterization of Complexity

Details Cayley Configuration Spaces of 1-dof Tree-decomposable Linkages, Part II: Combinatorial Characterization of Complexity Cayley Configuration Spaces of 1-dof Tree-decomposable Linkages, Part II: Combinatorial Characterization of Complexity

2011-12-27

arxiv.org/abs/1112.6009v2

Computer Science

Computational Geometry

Scientific paper

We continue the study of Cayley complexity of generic 1-dof linkages, i.e, the algebraic complexity of describing interval endpoints of the Cayley configuration space. Using the properties of these endpoints, we define in Part I a class of graphs G whose generic linkages have low Cayley complexity on a given non-edge f: i.e, all interval endpoints are QRS. Consider any non-edge f of a 1-dof linkage's underlying graph G for which G \cup f is tree-decomposable. Does the Cayley complexity depend on the choice of f? We answer this question in the negative. Specifically, we show that if the graph has low Cayley complexity over some choice of f, then it has low Cayley complexity for any choice of f. This shows that low Cayley complexity is a property of G (independent of non-edge f). Then, we give an combinatorial algorithmic characterization of graphs with low Cayley complexity. Next, we show a surprising result that (graph) planarity is equivalent to low Cayley complexity for a natural subclass of 1-dof triangle-decomposable linkages. While this is a finite forbidden minor graph characterization of low Cayley complexity, we provide counterexamples showing impossibility of such finite forbidden minor characterizations when the above subclass is enlarged.

Affiliated with

Also associated with

No associations

Rating

Cayley Configuration Spaces of 1-dof Tree-decomposable Linkages, Part II: Combinatorial Characterization of Complexity 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 Cayley Configuration Spaces of 1-dof Tree-decomposable Linkages, Part II: Combinatorial Characterization of Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cayley Configuration Spaces of 1-dof Tree-decomposable Linkages, Part II: Combinatorial Characterization of Complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-37615