Unconstrained Equivalents of Constrained Graphs.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1974
- Accession Number
- AD0779402
Entities
People
- J. Michael Yohe
Organizations
- University of Wisconsin–Madison