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. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 331-342(Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_28).

Full text not available from this repository.

Abstract

In octilinear drawings of planar graphs, every edge is drawn as an alternating sequence of horizontal, vertical and diagonal 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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_28
Classifications: G Algorithms and Complexity > G.210 Bends
G Algorithms and Complexity > G.280 Canonical Ordering
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.540 Planar
P Styles > P.600 Poly-line
P Styles > P.600 Poly-line > P.600.300 Mainly Orthogonal
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 22 May 2015 09:05
Last Modified: 22 May 2015 13:02
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1444

Actions (login required)

View Item View Item