A Sufficient Condition for Realizability of Constrained Graphs.

摘要

A constrained graph G is realizable if it is the intersection graph of a collection of arcs in the unit disk (D sup 2), where each arc is required to intersect exactly one (distinct) boundary point of (D sup 2), and the ordering of these boundary points is specified by the constraints on G. In this paper the author obtains a new sufficient condition for a constrained graph to be realizable. This extends work previously done by F. W. Sinden of Bell Labs.