A 2D geometric constraint solver using a graph reduction method

Samy Ait-Aoudia, Sebti Foufou

Research output: Contribution to journalArticlepeer-review


Modeling by constraints enables users to describe shapes by specifying relationships between geometric elements. These relationships are called constraints. A constraint solver derives then automatically the design intended by exploiting these constraints. The constraints solvers can be classified in four categories: symbolic, numerical, rule-oriented and graph-constructive solvers. The graph constructive approach is widely used in recent Computer Aided Design (CAD) systems. In this paper, we present a decomposition-recombination (DR) planning algorithm, called S-DR, that uses a graph reduction method to solve systems of 2D geometric constraints. Based on the key concept of skeletons, S-DR planner figures out a plan for decomposing a well constrained system into small sub-systems and recombines the solutions of these sub-systems to derive the solution of the entire system.

Original languageEnglish (US)
Pages (from-to)1187-1194
Number of pages8
JournalAdvances in Engineering Software
Issue number10-11
StatePublished - 2010


  • Decomposition-recombination (DR) planning
  • Geometric constraints
  • Graph algorithms
  • Graph-constructive solver
  • Modeling by constraints
  • Under-constrained problems

ASJC Scopus subject areas

  • Software
  • General Engineering


Dive into the research topics of 'A 2D geometric constraint solver using a graph reduction method'. Together they form a unique fingerprint.

Cite this