On intersection representations of co-planar graphs (Q1377831)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On intersection representations of co-planar graphs |
scientific article; zbMATH DE number 1110081
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On intersection representations of co-planar graphs |
scientific article; zbMATH DE number 1110081 |
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
