DIMACS Theoretical Computer Science Seminar


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.