$1$-string $B_2$-VPG representation of planar graphs

Therese Biedl, Martin Derka


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$. We also show that only a subset of the possible curve shapes is necessary to represent $4$-connected planar graphs.

Full Text:


DOI: http://dx.doi.org/10.20382/jocg.v7i2a8

ISSN: 1920-180X