Planar graphs have 1-string representations
From MaRDI portal
Publication:2380780
DOI10.1007/s00454-009-9196-9zbMath1221.05074OpenAlexW2167209773MaRDI QIDQ2380780
Jérémie Chalopin, Pascal Ochem, Daniel Gonçalves
Publication date: 12 April 2010
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-009-9196-9
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Unit disk representations of embedded trees, outerplanar and multi-legged graphs ⋮ Finding geometric representations of apex graphs is NP-hard ⋮ Maximum Independent Set on $$B_1$$ B 1 -VPG Graphs ⋮ Finding geometric representations of apex graphs is \textsf{NP}-hard ⋮ Order-Preserving 1-String Representations of Planar Graphs ⋮ Shorter Labeling Schemes for Planar Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Representations by contact and intersection of segments
- On grid intersection graphs
- Intersection graphs of curves in the plane
- A theorem on graphs
- Edge partition of planar sraphs into two outerplanar graphs
- Triangle-Free Planar Graphs and Segment Intersection Graphs
- Every planar graph is the intersection graph of segments in the plane