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. 331-342.

Abstract

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(n^2)×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.


Actions:
Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Proceedings article
Citations: No citation data.
Uncontrolled Keywords:
Subjects:
  • 68-XX Computer science

  • 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: 05 Sep 2014 15:34
    Last Modified: 24 Nov 2015 09:37
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/875