Título:
|
Treedecomposition of geometric constraint graphs based on computing graph circuits
|
Autor/a:
|
Tarres Puertas, Marta Isabel; Vila Marta, Sebastià; Joan Arinyo, Robert
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics; Universitat Politècnica de Catalunya. Departament de Disseny i Programació de Sistemes Electrònics; Universitat Politècnica de Catalunya. GIE - Grup d'Informàtica a l'Enginyeria |
Abstract:
|
The graph-based geometric constraint solving technique works in two steps. First the geometric problem is translated into a
graph whose vertices represent the set of geometric elements and whose edges are the constraints. Then the constraint
problem is solved by decomposing the graph into a collection
of subgraphs each representing a standard problem which is
solved by a dedicated equational solver.
In this work we report on an algorithm to decompose biconnected
tree-decomposable graphs representing either underor
wellconstrained 2D geometric constraint problems. The
algorithm recursively first computes a set of fundamental
circuits in the graph then splits the graph into a set of
subgraphs each sharing exactly three vertices with the fundamental
circuit. Practical experiments show that the reported
algorithm clearly outperforms the treedecomposition
approach based on identifying subgraphs by applying specific
decomposition rules. |
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica::Aplicacions de la informàtica -Computer graphics -Object-oriented methods (Computer science) -Infografia -Geometria computacional -Mètodes orientats a objectes (Informàtica) |
Derechos:
|
|
Tipo de documento:
|
Artículo - Versión presentada Objeto de conferencia |
Editor:
|
ACM Press, NY
|
Compartir:
|
|