On intersection representations of co-planar graphs (Q1377831)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On intersection representations of co-planar graphs |
scientific article |
Statements
On intersection representations of co-planar graphs (English)
0 references
19 October 1998
0 references
It is shown that the complement of a planar graph can be represented as the intersection graph of convex sets in the plane. As a consequence the authors obtain that the CLIQUE problem for intersection graphs of convex sets in the plane is NP-complete.
0 references
planar graph
0 references
intersection graph
0 references
CLIQUE problem
0 references
