×

INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs. (English) Zbl 0727.05056

In this paper the computational complexities of the INDEPENDENT SET and the CLIQUE problems are investigated when restricted to certain intersection graphs of segments in the plane. It turns out that finding a maximum independent set is NP-complete except for some very restricted cases - interval graphs and certain bipartite graphs. On the other hand a maximum clique can be found in polynomial time for intersection graphs of segments lying in at most k directions in the plane, for any fixed positive integer k. This requires, however, a suitable description of the representation.

MSC:

05C99 Graph theory
05C85 Graph algorithms (graph-theoretic aspects)