On intersection representations of co-planar graphs

DOI10.1016/S0012-365X(97)81834-1zbMath0897.05030MaRDI QIDQ1377831

Aleš Kuběna, Jan Kratochvíl

Publication date: 19 October 1998

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

intersection graphplanar graphCLIQUE problem

Mathematics Subject Classification ID

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

Related Items (7)

Intersection graphs of L-shapes and segments in the plane ⋮ Homothetic polygons and beyond: maximal cliques in intersection graphs ⋮ The clique problem in ray intersection graphs ⋮ Almost all string graphs are intersection graphs of plane convex sets ⋮ Segment representation of a subclass of co-planar graphs ⋮ Proper colorability of segment intersection graphs ⋮ On String Graph Limits and the Structure of a Typical String Graph

Cites Work

• A polynomial time circle packing algorithm
• Interval representations of planar graphs
• Random interval graphs
• String graphs. II: Recognizing string graphs is NP-hard
• String graphs requiring exponential representations
• The max clique problem in classes of string-graphs
• Intersection graphs of curves in the plane
• The four-colour theorem
• Every planar map is four colorable
• Topology of Thin Film RC Circuits
• Unnamed Item
• Unnamed Item

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