Maximum weight independent sets and cliques in intersection graphs of filaments

摘要

We describe a method of defining new families of graphs called G-mixed, using the way of partitioning the edge set of overlap graphs. Consider a hereditary family G of graphs. An oriented graph G(V,E) is called G-mixed if its edge set can be partitioned into two disjoint subsets E_1,E_2 such that G(V,E_1∈G,(V,E_2) is transitive and for every three vertices w,v,u if w→υ∈E_2 and (u,v) ∈E_1; the letter G is generic and is replaced by specific names. The G-mixed graphs have a polymial time algorithm to find maximum weight cliques, when G has such an algorithm. We define a new family of intersection graphs called interval-filament graphs which contain the polygon-circle graphs, the circle graphs, the chordal graphs and the cocomparability graphs. Let I be a family of intervals on a line L. In the plane, above L, construct to each interval i∈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∈I} is a family of interval filaments and its intersection graph is an interval-filament graph. We prove that a graph is an interval-filament graph iff its complement is a cointerval-mixed graph. Since cointerval graphs have a polynomial time algorithm to find maximum weight cliques, we can find maximum weight independent sets in interval-filament graphs using the algorithm for maximum weight cliques in cointerval-mixed graphs. Interval-filament graphs have also an algorithm to find maximum weight cliques. New families of intersection graphs of filaments are defined using families of circular-arcs of circle and