DIMACS TR: 2003-37
Perfect interval filament graphs
Authors: Fanica Gavril
ABSTRACT
Let I be a family of intervals on a line L. In the plane, above L,
construct to each interval i \in I a curve f_i connecting its two
endpoints, such that if two intervals are disjoint, their curves
do not intersect; FI={f_i | i \in I} is a family of interval filaments
and its intersection graph is an interval filament graph. The interval
filament graphs contain the polygon-circle graphs, the circle graphs,
the chordal graphs and the cocomparability graphs. Similar families of
intersection graphs of filaments can be defined using families of
circular-arcs of a circle and families of subtrees of a tree or of cactus.
In the present paper we describe polynomial time algorithms to find holes
and antiholes of a give parity in interval filament graphs, circular-arc
filament graphs and subtree filament graphs on a tree and on a cactus;
assuming that Berge's SPGC is true, these algorithms give polynomial
time algorithms to test for perfectness. In addition we describe polynomial
time algorithms to find minimum coverings by cliques for their subfamilies
of perfect graphs.
Paper available at ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-37.ps.gz
DIMACS Home Page