Title: On intersection representations of co-planar graphs
Abstract: We show that complements of planar graphs have intersection representations by convex sets in the plane, i.e., for every planar graph, one can assign convex sets in the plane to its vertices in such a way that two of the sets are disjoint if and only if the correspondning vertices are adjacent. This fact has a complexity consequence — it follows that the problem of determining the clique number of an intersection graph of convex sets in the plane is NP-hard. We note that the complexity of this problem for intersection graphs of straight line segments in the plane is unknown.
Publication Year: 1998
Publication Date: 1998-01-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 23
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot