Decomposition of geometric constraint graphs based on computing fundamental circuits. Correctness and complexity

作者：Joan Arinyo R^*; Tarres Puertas M; Vila Marta S

来源：Computer-Aided Design, 2014, 52: 1-16.

DOI：10.1016/j.cad.2014.02.006

• Geometric constraint solving
• Graph decomposition
• Fundamental circuits
• Bridges
• Planar embeddings

In geometric constraint solving, Decomposition Recombination solvers (DR-solvers) refer to a general solving approach where the problem is divided into a set of sub-problems, each sub-problem is recursively divided until reaching basic problems which are solved by a dedicated equational solver. Then the solution to the starting problem is computed by merging the solutions to the sub-problems. %26lt;br%26gt;Triangle- or tree-decomposition is one of the most widely used approaches in the decomposition step in DR-solvers. It may be seen as decomposing a graph into three subgraphs such that subgraphs pairwise share one graph vertex. Shared vertices are called hinges. Then a merging step places the geometry in each sub-problem with respect to the other two. %26lt;br%26gt;In this work we report on a new algorithm to decompose biconnected geometric constraint graphs by searching for hinges in fundamental circuits of a specific planar embedding of the constraint graph. We prove that the algorithm is correct.

• 出版日期2014-7