Planar Octilinear Drawings with One Bend Per Edge - Graph Drawing - page 331

of a result of Keszeghetal.[13],itturns outthatevery d -planar graph, with 3

≤ d ≤

8,
admits a planar octilinear drawing with at most two bends per edge; see Section 1. On
the other hand, every 3-planar graph on five or more vertices admits a planar octilinear
drawing in which all edges are bendless [6,12].
In this paper, we bridgethegap between the two aforementioned results. We prove
that every 4-planar graph admits a planar octilinear drawing with at most one bend per
edgeincubic area. We also show that every 5-planar graph also admits a planar octi-
linear drawing with at most one bend per edge, butour construction may require super-
polynomial area. Finally, we demonstrate an infinite class of 6-planar graphs whose
planar octilinear drawingsrequire at least two bends per edge.

Related Work. The research on the (planar) slope number of graphs focuses on mini-
mizing the number of used slopes (see e.g., [10,13,14,15,16]). Octilinear drawings can
be seen as a special case thereof, since only four slopes are used. Keszeghetal.[13]
showed that any d -planar graph admits a planar drawing with one bend per edge, in
which all edge-segments have at most 2 d different slopes. So, for d =4and d =5,we
reduce the number of different slopes from 8 and 10 to 4. They also proved that d -planar
graphs, d ≥ 3, admit planar drawings with two bends per edgethatrequire at most

d

2
different slopes. One can transfer this technique to the octilinear model and show that
any d -planar graph, with 3 ≤ d ≤ 8, admits a planar octilinear drawing with two bends
per edge. For d =3, Di Giacomo et al. [6] recently proved that any 3-planar graph
with n

5 vertices has a bendless planar drawing with at most 4 different slopes and
angular resolution ˀ/ 4 (see also [12]); their approach also yields octilinear drawings.
Tamassia [20] showed that one can minimize the total number of bends in orthogo-
nal drawings of embedded 4-planar graphs. However, minimizing the number of bends
over all embeddings of a 4-planar graph is NP-hard [7]. The core of Tamassia'sap-
proach is a min-cost flow algorithm that specifies the angles and the bends of the draw-
ing,producing an orthogonalrepresentation , and then computes the actual drawing by
specifying the drawing's exact coordinates. Tamassia'salgorithm can be employed to
produce a bend-minimum octilinear representation for any given embedded 8-planar
graph. However, a bend-minimum octilinear representation may not be realizable by a
corresponding planar octilinear drawing [4].
Biedl and Kant [2] showed that any 4-planar graph except the octahedron admits
a planar orthogonal drawing with at most two bends per edgeonan O ( n 2 ) integer
grid. Hence, the octilinear drawing model allows ustoreduce the number of bends per
edge at the cost of an increased area. On the other hand, not all 4-planar graphs admit
orthogonal drawings with one bend per edge; however, testing whether a 4-planar graph
admits such a drawing can be done in polynomial time [3]. In the context of metro-
map visualization, several approaches have been proposed to produce metro-maps using
octilinear or nearly-octilinear polylines; see e.g., [9,18,19].

≥

Preliminaries. In ouralgorithms, we incrementally construct the drawings similar to
the method of Kant [11]. We first employ the canonical order to cope with triconnected
graphs. Then, we extend them to biconnected graphs using the SPQR-tree and to simply
connected graphs using the BC-tree. In this section we briefly recall them.