H-graphs: A new representation for tree decompositions of graphs. (October 2015) - Hidalgo, Marta; Joan-Arinyo, Robert
Abstract: In geometric constraint solving, 2D well constrained geometric problems can be abstracted as Laman graphs. If the graph is tree decomposable, the constraint-based geometric problem can be solved by a Decomposition–Recombination planner based solver. In general decomposition and recombination steps can be completed only when steps on which they are dependent have already been completed. This fact naturally defines a hierarchy in the decomposition–recombination steps that traditional tree decomposition representations do not capture explicitly. In this work we introduce h-graphs, a new representation for decompositions of tree decomposable Laman graphs, which captures dependence relations between different tree decomposition steps. We show how h-graphs help in efficiently computing parameter ranges for which solution instances to well constrained, tree decomposable geometric constraint problems with one degree of freedom can actually be constructed. Highlights: h-graphs, a new representation for tree decompositions of constraints graph is presented. h-graphs explicitly capture construction steps dependencies in a tree decomposition. An application to speed up computing feasibility ranges for constraint parameters is described.