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