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)

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)

Recommendations

• Publication:3474685
• 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

• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• scientific article; zbMATH DE number 3981198 (Why is no real title available?)
• A polynomial time circle packing algorithm
• Every planar map is four colorable
• 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

(11)

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

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)