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

• A new algorithm to solve the 2D geometric constraint problem is described.
• The graph is decomposed according to a set of fundamental circuits.
• Fundamental circuits are induced by a spanning tree.
• We prove the algorithm soundness.
• The worst running time is quadratic with the number of geometric elements.

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.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.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.