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.


Actions:
Download: [img] PDF
Download (2MB)
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: No citation data.
Uncontrolled Keywords:
Subjects:
  • 68-XX Computer science > 68Wxx Algorithms

  • Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Related URLs:
    Deposit Information:
    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