Planar Octilinear Drawings with One Bend Per Edge
Bekos, Michael A. and Gronemann, Martin and Kaufmann, Michael and Krug, Robert
(2014)
Planar Octilinear Drawings with One Bend Per Edge.
Published In:
Graph Drawing: 22nd International Symposium, GD 2014, Lecture Notes in Computer Science. 8871 Springer 2014, pp. 331342.
Abstract
In octilinear drawings of planar graphs, every edge is drawn as an alternating sequence of horizontal, vertical and diagonal (45°) linesegments. In this paper, we study octilinear drawings of low edge complexity, i.e., with few bends per edge. A kplanar graph is a planar graph in which each vertex has degree less or equal to k. In particular, we prove that every 4planar graph admits a planar octilinear drawing with at most one bend per edge on an integer grid of size O(n^2)×O(n). For 5planar graphs, we prove that one bend per edge still suffices in order to construct planar octilinear drawings, but in superpolynomial area. However, for 6planar graphs we give a class of graphs whose planar octilinear drawings require at least two bends per edge.
Item Type:  Proceedings article 

Citations:  No citation data. 
Uncontrolled Keywords:  
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Related URLs: 
ZAIK Number:  UNSPECIFIED 

Depositing User:  Martin Gronemann 
Date Deposited:  05 Sep 2014 15:34 
Last Modified:  24 Nov 2015 09:37 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/875 