Order-preserving 1-string representations of planar graphs

DOI10.1007/978-3-319-51963-0_22MaRDI QIDQ2971141zbMATH OpenOpenAlexFDO

Authors Martin Derka, Therese 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)

Abstract: This paper considers 1-string representations of planar graphs that are order-preserving in the sense that the order of crossings along the curve representing vertex $v$ is the same as the order of edges in the clockwise order around $v$ in the planar embedding. We show that this does not exist for all planar graphs (not even for all planar 3-trees), but show existence for some subclasses of planar partial 3-trees. In particular, for outer-planar graphs it can be order-preserving and outer-string in the sense that all ends of strings are on the outside of the representation.

Recommendations

• 1-string B₂-VPG representation of planar graphs
• 1-string \(B_2\)-VPG representation of planar graphs
• String graphs requiring exponential representations
• scientific article; zbMATH DE number 3882450
• Representations of Planar Graphs

Cites work

• 1-string B₂-VPG representation of planar graphs
• An algorithm for the maximum weight independent set problem on outerstring graphs
• Approximating the pathwidth of outerplanar graphs
• Equilateral L-contact graphs
• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• scientific article; zbMATH DE number 739017 (Why is no real title available?)
• Intersection graphs of L-shapes and segments in the plane
• Intersection graphs of segments
• Linear-time algorithms for hole-free rectilinear proportional contact graph representations
• Planar graphs as VPG-graphs
• Planar graphs have 1-string representations
• Recognizing string graphs in NP
• String graphs. II: Recognizing string graphs is NP-hard
• The max clique problem in classes of string-graphs
• VPG and EPG bend-numbers of Halin graphs
• Weakly transitive orientations, Hasse diagrams and string graphs

Cited in

(5)

• scientific article; zbMATH DE number 6381690 (Why is no real title available?)
• 1-string B₂-VPG representation of planar graphs
• 1-string \(B_2\)-VPG representation of planar graphs
• Constrained outer-string representations
• Constrained outer-string representations

This page was built for publication: Order-preserving 1-string representations of planar graphs

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