Unconstrained Equivalents of Constrained Graphs.
Technical summary rept.,
WISCONSIN UNIV MADISON MATHEMATICS RESEARCH CENTER
Pagination or Media Count:
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
- Theoretical Mathematics