To access the full text documents, please follow this link: http://hdl.handle.net/2117/7779

Treedecomposition of geometric constraint graphs based on computing graph circuits
Tarres Puertas, Marta Isabel; Vila Marta, Sebastià; Joan Arinyo, Robert
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 en l'Enginyeria
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.
À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)
info:eu-repo/semantics/submittedVersion
info:eu-repo/semantics/conferenceObject
ACM Press, NY
         

Show full item record

Related documents

Other documents of the same author

Joan Arinyo, Robert; Tarres Puertas, Marta Isabel; Vila Marta, Sebastià
Joan Arinyo, Robert; Soto Riera, Antoni; Vila Marta, Sebastià
Joan Arinyo, Robert; Soto Riera, Antoni; Vila Marta, Sebastià; Vilaplana Pasto, Josep
Joan Arinyo, Robert; Soto Riera, Antoni; Vila Marta, Sebastià; Vilaplana Pasto, Josep
 

Coordination

 

Supporters