DIMACS TR: 2003-37

Perfect interval filament graphs

Authors: Fanica Gavril

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