1-string B₂-VPG representation of planar graphs

DOI10.4230/LIPICS.SOCG.2015.141MaRDI QIDQ5368682zbMATH OpenOpenAlexFDO

Authors Martin Derka, Therese Biedl

Publication date 10 October 2017

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

zbMATH Keywords

planar graphsgraph drawingstring graphsVPG graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: In this paper, we prove that every planar graph has a 1-string $B_2$-VPG representation---a string representation using paths in a rectangular grid that contain at most two bends. Furthermore, two paths representing vertices $u,v$ intersect precisely once whenever there is an edge between $u$ and $v$.

Recommendations

• 1-string \(B_2\)-VPG representation of planar graphs
• Planar graphs as VPG-graphs
• Planar graphs as VPG-graphs
• String graphs of \(k\)-bend paths on a grid
• Order-preserving 1-string representations of planar graphs

Cited in

(10)

• Planar graphs as VPG-graphs
• Splitting \(B_2\)-VPG graphs into outer-string and co-comparability graphs
• String graphs of \(k\)-bend paths on a grid
• \(B_0\)-VPG representation of AT-free outerplanar graphs
• 1-string \(B_2\)-VPG representation of planar graphs
• Order-preserving 1-string representations of planar graphs
• VPG and EPG bend-numbers of Halin graphs
• Planar graphs as VPG-graphs
• scientific article; zbMATH DE number 6381690 (Why is no real title available?)
• Bounds on the bend number of split and cocomparability graphs

This page was built for publication: 1-string \(B_2\)-VPG representation of planar graphs

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