A k -Tree Generalization that Characterizes Consistency of Dimensioned Engineering Drawings
Philip H. Todd · SIAM Journal on Discrete Mathematics · 1989
In the one-dimensional case (vertical or horizontal dimensioning of a parallel-sided object) a consistent engineering drawing is one whose graph is a tree. To extend this work to two dimensions, we define a new generalization of the k-tree, by relaxing the mutual adjacency condition on vertices adjacent to the new vertex in the usual inductive definition of the k-tree. We call these graphs r-trees. We also define a generalization of the cyclic property of graphs. A graph is r-cyclic if it contains a subgraph, all of whose vertices have degree greater than r. We prove that r-trees are maximal r-acyclic graphs. The graph theory yields an algorithm for detecting consistency in dimensioned drawings.