Combinatorial Analysis for CAD



Journal Title

Journal ISSN

Volume Title



Computer Aided Design software allows mechanical engineers and architects to design complicated systems by specifying geometric constraints on small building blocks. One goal of CAD software is to give users feedback on whether the specified constraints are consistent or not. To approach this problem, we model a design as a body-and-cad framework, turn the framework into a primitive cad graph, and then use a combinatorial property called [a,b]-sparsity to analyze body-and-cad rigidity. We work with an efficient algorithm called the [a,b]-pebble game to check [a, b]-sparsity using Knuth‘s algorithm for matroid partitioning in the pebble game. The [a, b]-pebble game additionally finds [a,b]-circuits which indicate minimal inconsistencies in the constraints. A categorization of the structures of these circuits can help in giving more intuitive feedback to CAD users. This thesis studies the structures of circuits from a combinatorial perspective. Three categories of circuits were identified previously, but it remained open if the categorization was complete. By systematic enumeration of [a,b]-sparse graphs, we find circuits not in the known categories. We present both statistical results on the enumeration and categorization of [a, b]-circuits and case studies on selected uncategorized circuits. We also offer theoretical analysis on the relationship between the structures of circuits and properties of an associated graph called the Knuth graph.



Matroidal circuit, Combinatorial Analysis, Computer Science