On the Realization of a Linear Graph Given Its Algebraic Specification
Lisa Auslander, Horace M. Trent · The Journal of the Acoustical Society of America · 1961
The following problem is discussed in this paper. Given an algebraic specification of an oriented linear graph in the form of a branch-mesh or branch-node matrix on any arbitrary basis, how does one proceed systematically to construct the graph? This rather basic problem has been considered by other authors and a few procedures have been described in the literature. On closer examination the problem is not simply one of finding any old procedure that will work but rather a question of finding an efficient procedure in terms of the time required by an analyst to carry through the computation. A new procedure is described which is believed to be quite efficient. This procedure is simple since matrix manipulations are limited primarily to the deletion of rows and columns and the other main manipulation is that of freehand drawing. The procedure is based upon the Decomposition Theorem published earlier and involves the notion of dividing a large graph into a sequence of small ones. A reassembly process then yields the desired result.