Title: Intersection Graphs of Interval Filaments
Speaker: Fanica Gavril, DIMACS
Date: November 24, 2003 3:30-4:30pm
Location: DIMACS Center, CoRE Bldg, Room 431, Seminar Room, Rutgers University, Busch Campus, Piscataway, NJ
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 (called filament) fi
connecting its two endpoints, such that fi remains within the limits of
i; the intersection graph H of FI={fi | i in I} is an interval filament
graph. The interval filament graphs contain the polygon-circle, the
chordal and the cocomparability graphs. The non-edges in the interval
filament graph H (i.e., the edges of coH) can be partitioned into two
disjoint subsets E1 (for disjoint intervals) and E2 (for containing
intervals) such that coH(V,E1) is a cointerval graph, coH(V,E2) is
transitive and for every three distinct vertices w,v,u if w-->v in E2
and (u,v) in E1 then (u,w) in E1.
We show that many problems having polynomial time algorithms on
the inteval graphs and on the cotransitive graphs, have also polynomial
time algorithms on the interval filament graphs; for example, finding a
maximum independent set, finding a maximum clique and finding induced
paths and holes of given parity.
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 a cactus.