Planar Octilinear Drawings with One Bend Per Edge
Bekos, Michael A. and Gronemann, Martin and Kaufmann, Michael and Krug, Robert
(2015)
Planar Octilinear Drawings with One Bend Per Edge.
Published in:
Journal of Graph Algorithms and Applications: Special Issue on Selected Papers from the 22nd International Symposium on Graph Drawing (GD2014).
ISSN 1526-1719
Abstract
In octilinear drawings of planar graphs, every edge is drawn as a 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 at most 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 for some edges.
Download: |
![]() Download (2MB) |
---|---|
Editorial actions: | ![]() |
Item Type: | 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: | 03 Nov 2015 12:43 |
Last Modified: | 03 Nov 2015 12:43 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/895 |