Circular-Arc Containment Graphs.

Loading...
Thumbnail Image

Files

TR_88-53.pdf (596.34 KB)
No. of downloads: 581

Publication or External Link

Date

1988

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.

Notes

Rights