Planar graphs have 1-string representations

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

zbMATH Keywords

planar graphsstrings

Mathematics Subject Classification ID

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