H-graphs: A new representation for tree decompositions of graphs. (October 2015)

• Record Type: Journal Article
• Authors: Hidalgo, Marta; Joan-Arinyo, Robert
• Is Part Of: Computer aided design. Volume 67/68(2015)
• Page Start: 38
• Page End: 47
• Publication Date: 2015-10
• Subjects: Parametric solid modeling -- Geometric constraint solving -- Constraint graphs -- Tree-decompositions -- Construction steps dependencies -- Parameter ranges; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2015.05.003
• Languages: English
• ISSNs: 0010-4485

Abstract

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.