1-string B₂-VPG representation of planar graphs

DOI10.4230/LIPICS.SOCG.2015.141zbMATH Open1378.68127arXiv1411.7277OpenAlexW2561495450MaRDI QIDQ5368682FDOQ5368682

Authors: Martin Derka, Therese Biedl 

Publication date: 10 October 2017

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$.

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

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

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)

Cited In (10)

• Bounds on the bend number of split and cocomparability graphs
• Title not available (Why is that?)
• String graphs of \(k\)-bend paths on a grid
• 1-string \(B_2\)-VPG representation of planar graphs
• Order-preserving 1-string representations of planar graphs
• Planar graphs as VPG-graphs
• VPG and EPG bend-numbers of Halin graphs
• Splitting \(B_2\)-VPG graphs into outer-string and co-comparability graphs
• Planar graphs as VPG-graphs
• \(B_0\)-VPG representation of AT-free outerplanar 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)