Planar Octilinear Drawings with One Bend Per Edge (Extended Draft Version)
Bekos, Michael A. and Gronemann, Martin and Kaufmann, Michael and Krug, Robert
(2014)
Planar Octilinear Drawings with One Bend Per Edge (Extended Draft Version).
Technical Report
Springer, 18 p.
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:  Paper (Technical Report) 

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:  05 Sep 2014 15:34 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/877 