Segment representation of a subclass of co-planar graphs

DOI10.1016/J.DISC.2012.01.024zbMATH Open1242.05067arXiv1011.1332OpenAlexW2073239009MaRDI QIDQ418892FDOQ418892

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

Publication date: 30 May 2012

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A partial k-arboretum of graphs with bounded treewidth
• Intersection graphs of segments
• On intersection representations of co-planar graphs
• Every planar graph is the intersection graph of segments in the plane
• Topology of Thin Film RC Circuits

Cited In (4)

• Intersection graphs of L-shapes and segments in the plane
• The clique problem in ray intersection graphs
• On Representation of Planar Graphs by Segments
• Intersections and circuits in sets of line 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)