Segment representation of a subclass of co-planar graphs

DOI10.1016/J.DISC.2012.01.024MaRDI QIDQ418892zbMATH OpenOpenAlexFDO

Authors Mathew C. Francis, Tomáš Vyskočil, Jan Kratochvíl

Publication date 30 May 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.1332

zbMATH Keywords

co-planar graphssegment graphsgeometric intersection graphspartial 2-trees

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: A graph is said to be a segment graph if its vertices can be mapped to line segments in the plane such that two vertices have an edge between them if and only if their corresponding line segments intersect. Kratochv'{i}l and Kubv{e}na [``On intersection representations of co-planar graphs, Discrete Mathematics, 178(1-3):251-255, 1998] asked the question of whether the complements of planar graphs are segment graphs. We show here that the complements of all partial 2-trees are segment graphs.

Recommendations

• scientific article; zbMATH DE number 739017
• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• Intersection graphs of segments
• Segment representations with small resolution
• On intersection representations of co-planar graphs

Cites work

• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• Intersection graphs of segments
• On intersection representations of co-planar graphs
• On six problems posed by Jarik Nešetřil
• Topology of Thin Film RC Circuits

Cited in

(4)

• The clique problem in ray intersection graphs
• Intersection graphs of L-shapes and segments in the plane
• Intersections and circuits in sets of line segments
• On Representation of Planar Graphs by Segments

This page was built for publication: Segment representation of a subclass of co-planar graphs

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