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)) x 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. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1007/978-3-662-45803-7_28 | GRAPH DRAWING (GD 2014) |
DocType | Volume | Issue |
Journal | 8871 | 2 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
17 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Michael A. Bekos | 1 | 0 | 0.34 |
Martin Gronemann | 2 | 26 | 7.96 |
Michael Kaufmann 0001 | 3 | 41 | 8.28 |
Robert Krug 0001 | 4 | 0 | 0.34 |