Algorithms for detecting dependencies and rigid subsystems for CAD

James Farre, Helena Kleinschmidt, Jessica Sidman, Audrey St. John, Stephanie Stark, Louis Theran, Xilin Yu

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Automated approaches for detecting dependencies in structures created with Computer Aided Design software are critical for developing robust solvers and providing informative user feedback. We model a set of geometric constraints with a bi-colored multigraph and give a graph-based pebble game algorithm that allows us to determine combinatorially if there are generic dependencies. We further use the pebble game to yield a decomposition of the graph into factor graphs which may be used to give a user detailed feedback about dependent substructures in a specific realization of a system of CAD constraints with non-generic properties.
Original languageEnglish
Pages (from-to)130-149
Number of pages20
JournalComputer Aided Geometric Design
Early online date28 Jun 2016
Publication statusPublished - 1 Oct 2016


  • Sparsity matroid
  • Pebble game algorithm
  • Cad constraints


Dive into the research topics of 'Algorithms for detecting dependencies and rigid subsystems for CAD'. Together they form a unique fingerprint.

Cite this