
Accession Number : AD0779402
Title : Unconstrained Equivalents of Constrained Graphs.
Descriptive Note : Technical summary rept.,
Corporate Author : WISCONSIN UNIV MADISON MATHEMATICS RESEARCH CENTER
Personal Author(s) : Yohe,J. M.
Report Date : MAR 1974
Pagination or Media Count : 27
Abstract : A constrained graph G is realizable if and only if it is the intersection graph for a collection of arcs lying on a disc and having the further property that each arc intersects the boundary of the disc, and that these intersections occur in the order prescribed by the constraints on G. In the paper the author proves that every constrained graph G containing n nodes can be embedded in an unconstrained graph (G bar) containing 6n + 1 nodes such that G is realizable if and only if (G bar) is the intersection graph of a collection of arcs in (E sup 2). (Author)
Descriptors : *GRAPHICS, TOPOLOGY, NETWORK FLOWS, CIRCUITS, THEOREMS
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE