Circular-Arc Containment Graphs.
Circular-Arc Containment Graphs.
Loading...
Files
Publication or External Link
Date
1988
Authors
Advisor
Citation
DRUM DOI
Abstract
We introduce a new class of containment graphs called circular- arc containment graphs. A graph is called a circular-arc containment graph if there exists a family of arcs on a circle, such that each vertex corresponds to an arc and two vertices are connected by an edge if and only if one of the corresponding arcs contains the other. We characterize this class of graphs by establishing its equivalence to another relatively new class of intersection graphs, called circular permutation graphs. Given a circulararc containment graph in the form of a family of arcs on a circle, we describe efficient algorithms for finding a maximum clique and a maximum independent set of the graph.