2014/08/25 by Bekos, Michael A., Gronemann, Martin, Kaufmann, Michael +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1408.5920
In octilinear drawings of planar graphs, every edge is drawn as an alternating sequence of horizontal, vertical and diagonal (45^∘) line-segments. In this paper, we study octilinear drawings of low edge complexity, i.e., with few bends per edge. A k-planar graph is a planar graph in which each vertex has degree less or equal to k. In particular, we prove that every 4-planar graph admits a planar octilinear drawing with at most one bend per edge on an integer grid of size O(n2) × O(n). For 5-planar graphs, we prove that one bend per edge still suffices in order to construct planar octilinear drawings, but in super-polynomial area. However, for 6-planar graphs we give a class of graphs whose planar octilinear drawings require at least two bends per edge.