Order-Preserving 1-String Representations of Planar Graphs

DOI10.1007/978-3-319-51963-0_22zbMath1450.05058arXiv1609.08132OpenAlexW2526563325MaRDI QIDQ2971141

Martin Derka, Therese C. Biedl

Publication date: 4 April 2017

Published in: SOFSEM 2017: Theory and Practice of Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

outer-planar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• Intersection graphs of L-shapes and segments in the plane
• Approximating the pathwidth of outerplanar graphs
• VPG and EPG bend-numbers of Halin graphs
• Linear-time algorithms for hole-free rectilinear proportional contact graph representations
• An algorithm for the maximum weight independent set problem on outerstring graphs
• Weakly transitive orientations, Hasse diagrams and string graphs
• String graphs. II: Recognizing string graphs is NP-hard
• The max clique problem in classes of string-graphs
• Intersection graphs of segments
• Planar graphs have 1-string representations
• Planar Graphs as VPG-Graphs
• Equilateral L-Contact Graphs
• $1$-string $B_2$-VPG representation of planar graphs
• Every planar graph is the intersection graph of segments in the plane
• Recognizing string graphs in NP

This page was built for publication: Order-Preserving 1-String Representations of Planar Graphs