On intersection representations of co-planar graphs

DOI10.1016/S0012-365X(97)81834-1MaRDI QIDQ1377831zbMATH OpenFDO

Authors Aleš Kuběna, Jan Kratochvíl

Publication date 19 October 1998

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(97)81834-1

zbMATH Keywords

CLIQUE problemintersection graphplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (including graph drawing) in computer science (68R10)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 4142090
• A special planar satisfiability problem and a consequence of its NP- completeness
• scientific article; zbMATH DE number 4200260
• Convex Polygon Intersection Graphs
• Every planar graph is the intersection graph of segments in the plane (extended abstract)

Cites work

• A polynomial time circle packing algorithm
• Every planar map is four colorable
• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• scientific article; zbMATH DE number 3981198 (Why is no real title available?)
• Intersection graphs of curves in the plane
• Interval representations of planar graphs
• Random interval graphs
• String graphs requiring exponential representations
• String graphs. II: Recognizing string graphs is NP-hard
• The four-colour theorem
• The max clique problem in classes of string-graphs
• Topology of Thin Film RC Circuits

Cited in

(12)

• Homothetic polygons and beyond: maximal cliques in intersection graphs
• Almost all string graphs are intersection graphs of plane convex sets
• Intersection graphs of L-shapes and segments in the plane
• Intersection-link representations of graphs
• On string graph limits and the structure of a typical string graph
• The clique problem in ray intersection graphs
• Segment representation of a subclass of co-planar graphs
• scientific article; zbMATH DE number 6850320 (Why is no real title available?)
• Intersection-link representations of graphs
• Proper colorability of segment intersection graphs
• Proper colorability of segment intersection graphs
• Recognition and proper coloring of unit segment intersection graphs

This page was built for publication: On intersection representations of co-planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377831)