4-connected planar graphs are in $B_3$-EPG

Autor:	Biedl, Therese, Pennarun, Claire
Rok vydání:	2017
Předmět:	Computer Science - Computational Geometry
Druh dokumentu:	Working Paper
Popis:	We show that every 4-connected planar graph has a $B_3$-EPG representation, i.e., every vertex is represented by a curve on the grid with at most three bends, and two vertices are adjacent if and only if the corresponding curves share an edge of the grid. Our construction is based on a modification of the representation by touching thickened $L$-shapes proposed by Gon\c{c}alves et al.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1710.04583 Zobrazit plný text záznamu View this record from Arxiv