On the Total Number of Bends for Planar Octilinear Drawings

Abstract

An octilinear drawing of a planar graph is one in which each edge is drawn as a sequence of horizontal, vertical and diagonal at $45^\circ$ line-segments. For such drawings to be readable, special care is needed in order to keep the number of bends small. As the problem of finding planar octilinear drawings of minimum number of bends is NP-hard, in this paper we focus on upper and lower bounds. From a recent result of Keszegh et al. on the slope number of planar graphs, we can derive an upper bound of $4n-10$ bends for 8-planar graphs with n vertices. We considerably improve this general bound and corresponding previous ones for triconnected 4-, 5- and 6-planar graphs. We also derive non-trivial lower bounds for these three classes of graphs by a technique inspired by the network flow formulation of Tamassia.

This work has been supported by DFG grant Ka812/17-1.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Motivation and Background

Octilinear drawings of graphs have a long history of research, which dates back to the early thirties of the last century, when an English technical draftsman, Henry Charles Beck (also known as Harry Beck), designed the first schematic map of London Underground. His map, the so-called Tube map, looked more like an electrical circuit diagram (consisting of horizontal, vertical and diagonal line segments) rather than a true map, as the underlying geographic accuracy was neglected. Laying out networks in such a way is called octilinear graph drawing. In particular, an octilinear drawing $\varGamma (G)$ of a graph $G=(V,E)$ is one in which each vertex occupies a point on an integer grid and each edge is drawn as a sequence of horizontal, vertical and diagonal at $45^\circ$ line segments.

In planar octilinear graph drawing, an important goal is to keep the number of bends small, so that the produced drawings can be understood easily. However, the problem of determining whether a given embedded planar graph of maximum degree eight admits a bend-less planar octilinear drawing is NP-complete [16]. This motivated us to neglect optimality and study upper and lower bounds on the total number of bends of such drawings. Surprisingly enough, very few results were known, even if the octilinear model has been extensively studied in the areas of metro-map visualization and map schematization.

One can derive the first (non-trivial) upper bound on the required number of bends from a result on the planar slope number of graphs by Keszegh et al. [14], who proved that every k-planar graph (that is, planar of maximum degree k) has a planar drawing with at most $\lceil \frac{k}{2}\rceil$ different slopes in which each edge has two bends. For $3 \le k \le 8$, the drawings are octilinear, which yields an upper bound of $6n-12$, where n is the number of vertices of the graph. This bound can be reduced to $4n-10$ as follows. The edge that “enters” a vertex from its south port and the edge that “leaves” each vertex from its top port in the s-t ordering of the algorithm of Keszegh et al. can both be drawn with one bend each. This leads to a reduction by $2n-2$ bends and the bound of $4n-10$ follows.

On the other hand, it is known that every 3-planar graph with five or more vertices admits a planar octilinear drawing in which all edges are bend-less [8, 13]. Recently, it was proved that 4- and 5-planar graphs admit planar octilinear drawings with at most one bend per edge [2], which implies that their total number of bends can be upper bounded by 2n and 5n / 2, respectively.

Table 1. A short summary of our results.

Octilinear drawings form a natural extension of the so-called orthogonal drawings, which allow for horizontal and vertical edge segments only. For such drawings, several bounds on the total number of bends are given, see e.g., [4, 5, 15, 18]. It is also known that the bend minimization problem can be solved efficiently, when the input graph is embedded [17], while the corresponding minimizaton problem over all embeddings is NP-hard [11]. In [17], the author describes how one can extend his approach, so to compute a bend-optimal octilinear representation of any given embedded 8-planar graph. However, such a representation may not be realizable by a corresponding planar octilinear drawing [6].

The remainder of this paper is organized as follows. In Sect. 2, we recall basic definitions. In Sect. 3, we improve all aforementioned bounds for the classes of triconnected 4-, 5- and 6-planar graphs. In Sect. 4, we present lower bounds for these classes of planar graphs. We conclude in Sect. 5 with open problems. For a summary of our results refer to Table 1.

2 Preliminaries

Let $G=(V,E)$ be a triconnected planar graph and let $\varPi = (P_0,\ldots ,P_m)$ be a partition of V into paths, such that $P_0 = \{v_1,v_2\}$, $P_m=\{v_n\}$ and $v_2 \rightarrow v_1 \rightarrow v_n$ is a path on the outerface of G. For $k=0,1,\ldots ,m$, let $G_k$ be the subgraph induced by $\cup _{i=0}^k P_i$. Partition $\varPi$ is a canonical order [7, 12] of G if the following hold: (i) $G_k$ is biconnected, (ii) all neighbors of $P_k$ in $G_{k-1}$ are on the outer face of $G_{k-1}$ and (iii) all vertices of $P_k$ have at least one neighbor in $P_j$ for some $j > k$. $P_k$ is called singleton if $|P_k|=1$ and chain otherwise.

To simplify the description of our algorithms, we direct and color the edges of G based on $\varPi$ (similar to Schnyder colorings [9]) as follows. The first path $P_0$ of $\varPi$ consists of exclusively one edge (that is, edge $(v_1,v_2)$), which we color blue and direct towards vertex $v_1$. For each path $P_k=\{v_i, \ldots , v_{i+j}\} \in \varPi$ later in the order, let $v_\ell$ and $v_r$ be the leftmost and rightmost neighbors of $P_k$ in $G_{k-1}$, respectively. In the case where $P_k$ is a chain (that is, $j > 0$), we color edge $(v_i,v_\ell )$ and all edges of $P_k$ blue and direct them towards $v_\ell$. The edge $(v_{i+j},v_r)$ is colored green and is directed towards $v_r$ (see Fig. 1a). In the case where $P_k$ is a singleton (that is, $j = 0$), we color the edges $(v_i,v_\ell )$ and $(v_{i},v_r)$ blue and green, respectively and we direct them towards $v_\ell$ and $v_r$. We color the remaining edges of $P_k$ that are incident to $G_{k-1}$ (if any) red and we direct them towards $v_i$ (see Fig. 1e). Given a vertex $v \in V$ of G, we denote by $\mathrm {indeg}_{\mathrm {x}}(v)$ ($\mathrm {outdeg}_{\mathrm {x}}(v)$, resp.) the in-degree (out-degree, resp.) of vertex v in color $x \in \{r,b,g\}$.

3 Upper Bounds

3.1 Triconnected 4-Planar Graphs

Let $G=(V,E)$ be a triconnected 4-planar graph. Before we proceed with the description of our approach, we need to define two useful notions. First, a vertical cut is a y-monotone continuous curve that crosses only horizontal segments and divides a drawing into a left and a right part; see e.g. [10]. Such a cut makes a drawing horizontally stretchable in the following sense: One can shift the right part of the drawing that is defined by the vertical cut further to the right while keeping the left part of the drawing in place and the result is a valid octilinear drawing. Similarly, a horizontal cut is defined. Since G has at most 2n edges, it follows that G has at most $n+2$ faces. In order to construct a drawing $\varGamma (G)$ of G, which has roughly at most $n+2$ bends, we also need to associate to each face of G a so-called reference edge. This is done as follows.

Let $\varPi = \{P_0, \ldots , P_m \}$ be a canonical order of G and assume that $\varGamma (G)$ is constructed incrementally by placing a new path of $\varPi$ each time, so that the boundary of the drawing constructed so far is a x-monotone path. When placing a new path $P_k \in \varPi$, $k=1,\ldots ,m-1$, one or two bounded faces of G are formed (note that we treat the last partition $P_m$ of $\varPi$ separately). More precisely, if $P_k$ is a chain or a singleton of degree 3 in $G_k$, then only one bounded face is formed. Otherwise (that is, $P_k$ is a singleton of degree 4 in $G_k$), two new bounded faces are formed. In both cases, each newly-formed bounded face consists of at least two edges incident to vertices of $P_k$ and at least one edge of $G_{k-1}$. In the former case, the reference edge of the newly-formed bounded face, say f, is defined as follows. If f contains at least one green edge that belongs to $G_{k-1}$, then the reference edge of f is the leftmost such edge (see Fig. 1a and c). Otherwise, the reference edge of f is the leftmost blue edge of f that belongs to $G_{k-1}$ (see Fig. 1b and d). In the case where $P_k$ is a singleton of degree 4 in $G_k$, the reference edge of each of the newly formed faces is the edge of $G_{k-1}$ that is incident to the endpoint of the red edge involved.

Fig. 1.

Illustration of the reference edge (bold drawn) in the case of: (a-b) a chain, (c-d) a singleton of degree 2 in $G_k$ and (e) a singleton of degree 3 in $G_k$.

As already stated, we will construct $\varGamma (G)$ in an incremental manner by placing one partition of $\varPi$ at a time. For the base, we momentarily neglect edge $(v_1, v_2)$ of the first partition $P_0$ of $\varPi$ and we start by placing the second one, say a chain $P_1 = \{v_3 , \ldots ,v_{|P_1|+2} \}$, on a horizontal line from left to right. Since by definition of $\varPi$, $v_3$ and $v_{|P_1|+2}$ are adjacent to the two vertices, $v_1$ and $v_2$, of the first partition $P_0$, we place $v_1$ to the left of $v_3$ and $v_2$ to the right of $v_{|P_1|+2}$. So, they form a single chain where all edges are drawn using horizontal line segments that are attached to the east and west port at their endpoints. The case where $P_1$ is a singleton is analogous. Assume now that we have already constructed a drawing for $G_{k-1}$ which has the following invariant properties:

• IP-1: The number of edges of $G_{k-1}$ with a bend is at most equal to the number of reference edges in $G_{k-1}$.

• IP-2: The north-west, north and north-east (south-west, south and south-east) ports of each vertex are occupied by incoming (outgoing) blue and green edges and by outgoing (incoming) red edges¹.

• IP-3: If a horizontal port of a vertex is occupied, then it is occupied either by an edge with a bend (to support vertical cuts) or by an edge of a chain.

• IP-4: A red edge is not on the outerface of $G_{k-1}$.

• IP-5: A blue (green, resp.) edge of $G_{k-1}$ is never incident to the north-west (north-east, resp.) port of a vertex of $G_{k-1}$.

• IP-6: From each reference edge on the outerface of $G_{k-1}$ one can devise a vertical cut through the drawing of $G_{k-1}$.

The base of our algorithm conforms with the aforementioned invariant properties. Next, we consider the three main cases.

• C.1: $P_k = \{ v_i \}$ is a singleton of degree 2 in $G_k$. Let $v_\ell$ and $v_r$ be the leftmost and rightmost neighbors of $v_i$ in $G_{k-1}$. We claim that the north-east port of $v_\ell$ and the north-west port of $v_r$ cannot be simultaneously occupied. Assume to the contrary that the claim does not hold and denote by $v_\ell \rightsquigarrow v_r$ the path from $v_\ell$ to $v_r$ at the outerface of $G_{k-1}$ (neglecting the direction of the edges). By IP-5, $v_\ell \rightsquigarrow v_r$ starts as blue from the north-east port of $v_\ell$ and ends as green at the north-west port of $v_r$. So, inbetween there is a vertex of the path $v_\ell \rightsquigarrow v_r$ which has a neighbor in $P_j$ for some $j \ge k$; a contradiction to the degree of $v_i$. W.l.o.g. assume that the north-east port of $v_\ell$ is unoccupied. If $(v_i,v_\ell )$ is the reference edge of a face, then we draw $(v_i,v_\ell )$ as a horizontal-diagonal combination from the west port of $v_i$ towards the north-east port of $v_\ell$. Otherwise, $(v_i,v_\ell )$ is drawn bend-less from the south-west port of $v_i$ towards the north-east port of $v_\ell$. To draw the edge $(v_i,v_r)$, again we distinguish two cases. If the north-west port at $v_r$ is unoccupied, then $(v_i,v_r)$ will use this port at $v_r$. Otherwise, $(v_i,v_r)$ will use the north port at $v_r$. In addition, if $(v_i,v_r)$ is the reference edge of a face, then $(v_i,v_r)$ will use the east port at $v_i$. Otherwise, the south-east port at $v_i$. The port assignment described above conforms to IP-2–5. Clearly, IP-1 also holds. IP-6 holds because the newly introduced edges that are reference edges have a horizontal segment, which inductively implies that vertical cuts through them are possible.

• C.2: $P_k = \{v_i\}$ is a singleton of degree 3 in $G_k$. This is the most involved case. However, due to space constraints we give the details in [3].

• C.3: $P_k=\{v_i,\ldots v_{i+j}\}$ ; $j \ge 1$ is a chain. This case is similar to case C.1, as $P_k$ has exactly two neighbors in $G_{k-1}$, which we denote by $v_\ell$ and $v_r$. The edges between $v_i,\ldots ,v_{i+j}$ will be drawn as horizontal segments connecting the west and east ports of the respective vertices. Edges $(v_i,v_\ell )$ and $(v_{i+j},v_r)$ are drawn based on the rules of the corresponding case of a singleton with two neighbors in $G_{k-1}$. The port assignment still conforms to IP-2–IP-5. IP-1 and IP-6 hold, since all edges of the chain are horizontal.

Note that the coordinates of the newly introduced vertices are determined by the shape of the edges connecting them to $G_{k-1}$. If there is not enough space between $v_\ell$ and $v_r$ to accommodate the new vertices, IP-6 allows us to stretch the drawing horizontally using the reference edge of the newly formed face.

If $v_n$ is of degree 3, we cope with the last partition $P_m = \{v_n\}$ as being an ordinary singleton. Otherwise (i.e., $v_n$ is of degree 4), we momentarily ignore $(v_n,v_1)$ and proceed to draw the remaining edges incident to $v_n$. Edge $(v_n,v_1)$ can be drawn afterwards using two bends. Since by construction $v_1$ and $v_2$ are horizontally aligned, we can draw the edge $(v_1,v_2)$ with a single bend, emanating from the south-east port of $v_1$ towards the south-west port of $v_2$.

Theorem 1

Let G be a triconnected 4-planar graph with n vertices. A planar octilinear drawing $\varGamma (G)$ with at most $n+5$ bends can be computed in O(n) time.

Proof

By IP-1, all bends of $\varGamma (G)$ are in correspondence with the reference edges of G, except for the bends of $(v_1,v_2)$ and $(v_n,v_1)$. Since the number of reference edges is at most $n+2$ and the edges $(v_1,v_2)$ and $(v_n,v_1)$ require 3 additional bends, the total number of bends of $\varGamma (G)$ does not exceed $n+5$. The linear running time follows by adopting the shifting method of Kant [13] to compute the actual coordinates of the vertices of G.   $\square$

3.2 Triconnected 5-Planar Graphs

Our algorithm for triconnected 5-planar graphs is an extension of an algorithm of Bekos et al. [2], which computes for a given triconnected 5-planar graph G on n vertices a planar octilinear drawing $\varGamma (G)$ of G with at most one bend per edge. Since G cannot have more than 5n / 2 edges, it follows that the total number of bends of $\varGamma (G)$ is at most 5n / 2. However, before we proceed with the description of our extension, we first provide some insights into this algorithm, which is based on a canonical order $\varPi$ of G. Central are IP-2 and IP-4 of the previous section and the so-called stretchability invariant, according to which all edges on the outerface of the drawing constructed at some step of the canonical order have a horizontal segment and therefore one can devise corresponding vertical cuts to horizontally stretch the drawing. We claim that we can appropriately modify this algorithm, so that all red edges of $\varPi$ are bend-less.

Since we seek to draw all red edges of $\varPi$ bend-less, our modification is limited to singletons. So, let $P_k = \{ v_i \}$ be a singleton of $\varPi$. The degree restriction implies that $v_i$ has at most two incoming red edges (we also assume that $P_k$ is not the last partition of $\varPi$, that is $k \ne m$). We first consider the case where $v_i$ has exactly one incoming red edge, say $e=(v_j,v_i)$, with $j<i$. By construction, e must be attached to one of the northern ports of $v_j$ (that is, north-west, north or north-east). On the other hand, e can be attached to any of the southern ports of $v_i$, as e is its only incoming red edge. This guarantees that e can be drawn bend-less. Due to space constraints, the more involved case, according to which $v_i$ has exactly two incoming red edges, is discussed in [3].

Theorem 2

Let G be a triconnected 5-planar graph with n vertices. A planar octilinear drawing $\varGamma (G)$ with at most $2n-2$ bends can be computed in O(n) time.

Proof

The only edges of $\varGamma (G)$ that have a bend are the blue and the green ones and possibly the third incoming red edge of vertex $v_n$ of the last partition $P_m$ of $\varPi$. Hence, $2n-2$ at most. The running time remains linear since the shifting technique can still be applied.    $\square$

3.3 Triconnected 6-Planar Graphs

We present an algorithm that based on a canonical order $\varPi =\{ P_0, \ldots , P_m \}$ of a given triconnected 6-planar graph G results in a drawing $\varGamma (G)$ of G, in which each edge has at most two bends. So, in total $\varGamma (G)$ has $6n-12$ bends. Then, we appropriately adjust $\varGamma (G)$ to reduce the total number of bends.

Fig. 2.

(a)-(f) Illustration of the port assignment computed by Algorithm 1. (g)-(k) Different segment combinations with at most two bends (horizontal ones are drawn dotted)

Algorithm 1 describes rules R1 - R6 to assign the edges to the ports of the corresponding vertices. It is not difficult to see that all port combinations implied by these rules can be realized with at most two bends, so that all edges have a horizontal segment (which makes the drawing horizontally stretchable): (i) a blue edge emanates from the west or south-west port of a vertex (by rule R4) and leads to one of the south-east, east, north-east, north or north-west ports of its other endvertex (by rule R1); see Fig. 2g and h, (ii) a green edge emanates from the east or south-east port of a vertex (by rule R5) and leads to one of the west, north-west, north or north-east ports of its other endvertex (by rule R3); see Fig. 2i and j, (iii) a red edge emanates from one of the north-west, north, north-east ports of a vertex (by rule R2) and leads to one of the south-west, south, south-east ports of its other endvertex (by rule R6); see Fig. 2k.

The shape of each edge is completely determined by the aforementioned rules. To compute the actual drawing $\varGamma (G)$ of G, we follow an incremental approach according to which one partition (that is, a singleton or a chain) of $\varPi$ is placed at a time, similar to Kant’s approach [12] and the 4- or 5-planar case. Each edge is drawn based on its shape, while the horizontal stretchability ensures that potential crossings can always be eliminated. Note additionally that we adopt the leftist canonical order [1].

We reduce the total number of bends in two steps. In the first step, we show that all red edges can be drawn with at most one bend each. Recall that a red edge emanates from one of the north-west, north, north-east ports of a vertex and leads to one of the south-west, south, south-east ports of its other-endvertex. So, in order to prove that all red edges can be drawn with at most one bend each, we have to consider in total nine cases, which are illustrated in Fig. 3. It is not difficult to see that in each of these cases, the red edge can be drawn with at most one bend. Note that the absence of horizontal segments at the red edges does not affect the stretchability of $\varGamma (G)$, since each face of $\varGamma (G)$ has at most two such edges (which both “point upward” at a common vertex). Since a red edge cannot be incident to the outerface of any intermediate drawing constructed during the incremental construction of $\varGamma (G)$, it follows that it is always possible to use only horizontal segments (of blue and green edges) to define vertical cuts, thus, avoiding all red edges.

Fig. 3.

Red edges can be redrawn with one bend (in boxes we show their initial shapes)

The second step of our bend reduction is more involved. We seek to “save” two bends per vertex², which yields a reduction by roughly 2n bends in total. Consider an arbitrary vertex $u \in V$ of G. Our goal is to prove that there always exist two edges incident to u, which can be drawn with only one bend each. By rules R3 and R4, it follows that the west port of vertex u is always occupied, either by an incoming green edge (by rule R3) or by a blue outgoing edge (by rule R4; $u \ne v_1 \in P_0$). Analogously, the east port of vertex u is always occupied; either by a blue incoming edge (by rules R1 and R2) or by an outgoing green edge (by rule R5). Let $(u,v) \in E$ be the edge attached at the west port of u (symmetrically we cope with the edge at the east port of u). If edge (u, v) is attached to a non-horizontal port at v, then (u, v) is by construction drawn with one bend (regardless of its color; see Fig. 2g and i) and our claim follows.

It remains to consider the case where (u, v) is attached to a horizontal port at v. Assume first that (u, v) is blue (we discuss the case where (u, v) is green later). By Algorithm 1, it follows that (u, v) is either the first blue incoming edge attached at v (by rules R1b and R1c) or the second one (by rule R1a). We consider each of these cases separately. In rule R1c, observe that (u, v) is part of a chain (because $\mathrm {outdeg}_{\mathrm {g}}(u)=0$). Hence, when placing this chain in the canonical order, we will place u directly to the right of v. This implies that (u, v) will be drawn as a horizontal line segment (that is, bend-less). Similarly, we cope with rule R1b, when additionally $\mathrm {outdeg}_{\mathrm {g}}(u)=0$. So, there are still two cases to consider: rule R1a and rule R1b, when additionally $\mathrm {outdeg}_{\mathrm {g}}(u)=1$; see the left part of Fig. 4. In both cases, the current degree of vertex u is 3 and vertex v (and other vertices that are potentially horizontally-aligned with v) must be shifted diagonally up, when u is placed based on the canonical order, such that (u, v) is drawn as a horizontal line segment (that is, bend-less; see the right part of Fig. 4). Note that when v is shifted up, vertex v and all vertices that are potentially horizontally-aligned with v are also of degree 3, since otherwise one of these vertices would not have a neighbor in some later partition of $\varPi$, which contradicts the definition of $\varPi$.

Fig. 4.

Aligning vertices u and v.

We complete our case analysis with the case where (u, v) is green. By rule R3a, it follows that (u, v) is the first green incoming edge attached at u. In addition, when (u, v) is placed based on the canonical order, there is no red outgoing edge attached at u. The leftist canonical order also ensures that there is no blue incoming edge at u drawn before (u, v). Hence, u is of degree two, when edge (u, v) is placed, which guarantees that v can be shifted up (potentially with other vertices that are horizontally-aligned with u), such that (u, v) is drawn as a horizontal line segment. We summarize our approach in the following theorem.

Theorem 3

Let G be a triconnected 6-planar graph with n vertices. A planar octilinear drawing $\varGamma (G)$ with at most $3n-8$ bends can be computed in $O(n^2)$ time.

Proof

Before the two bend-reduction steps, $\varGamma (G)$ contains at most $6n-12$ bends. In the first reduction step, all red edges are drawn with one bend. Hence, $\varGamma (G)$ contains at most $5n-9$ bends. In the second reduction step, we “save” two bends per vertex (except for $v_1 \in P_0$), which yields a reduction by $2n-1$ bends. So, in total $\varGamma (G)$ contains at most $3n-8$ bends. On the negative side, we cannot keep the running time of our algorithm linear. The reason is the second reduction step, which yields changes in the y-coordinates of the vertices. In the worst case, however, quadratic time suffices.    $\square$

Note that there exist 6-planar graphs that do not admit planar octilinear drawings with at most one bend per edge [2]. Theorem 3 implies that on average one bend per edge suffices.

4 Lower Bounds

4.1 4-Planar Graphs

We start our study with the case of 4-planar graphs. Our main observation is that if a 3-cycle $\mathcal {C}_3$ of a graph has at least two vertices, with at least one neighbor in the interior of $\mathcal {C}_3$ each, then at least one edge of $\mathcal {C}_3$ must contain a bend, since the sum of the interior angles at the corners of $\mathcal {C}_3$ exceeds $180^\circ$. In fact, elementary geometry implies that a k-cycle, say $\mathcal {C}_k$ with $k \ge 3$, whose vertices have $\sigma \ge 0$ neighbors in the interior of $\mathcal {C}_k$ requires (at least) $\max \{0, \lceil (\sigma -3k + 8)/3 \rceil \}$ bends. Therefore, a bend is necessary. Now, refer to the 4-planar graph of Fig. 5a, which contains n / 3 nested triangles, where n is the number of its vertices. It follows that this particular graph requires at least $n/3-1$ bends in total.

4.2 5- and 6-Planar Graphs

For these classes of graphs, we follow an approach inspired by Tamassia’s min-cost flow formulation [17] for computing bend-minimum representations of embedded planar graphs of bounded degree. Since it is rather difficult to implement this algorithm in the case where the underlying drawing model is not the orthogonal model, we developed an ILP instead. Recall that a representation describes the “shape” of a drawing without specifying its exact geometry. This is enough to determine a lower bound on the number of bends, even if a bend-optimal octilinear representation may not be realizable by a corresponding (planar) octilinear drawing.

In our formulation, variable $\alpha (u,v) \cdot 45^\circ$ corresponds to the angle formed at vertex u by edge (u, v) and its cyclic predecessor around vertex u. Hence, $1 \le \alpha (u,v) \le 8$. Since the sum of the angles around a vertex is $360^\circ$, it follows that $\sum _{v \in N(u)}a(u,v) = 8$. Given an edge $e=(u,v)$, variables $\ell _{45}(u,v)$, $\ell _{90}(u,v)$ and $\ell _{135}(u,v)$ correspond to the number of left turns at $45^\circ$, $90^\circ$ and $135^\circ$ when moving along (u, v) from vertex u towards vertex v. Similarly, variables $r_{45}(u,v)$, $r_{90}(u,v)$ and $r_{135}(u,v)$ are defined for right turns. All aforementioned variables are integer lower-bounded by zero. For a face f, we assume that its edges are directed according to the clockwise traversal of f. This implies that each (undirected) edge of the graph appears twice in our formulation. For reasons of symmetry, we require $\ell _{45}(u,v) = r_{45}(v,u)$, $\ell _{90}(u,v) = r_{90}(v,u)$ and $\ell _{135}(u,v) = r_{135}(v,u)$. Since the sum of the angles formed at the vertices and at the bends of a bounded face f equals to $180^\circ \cdot (p(f)-2)$, where p(f) denotes the total number of such angles, it follows that $\sum _{(u,v) \in E(f)}\alpha (u,v)+(\ell _{45}(u,v)+\ell _{90}(u,v)+\ell _{135}(u,v)) - (r_{45}(u,v)+r_{90}(u,v)+r_{135}(u,v))=4a(f)-8$, where a(f) denotes the total number of vertex angles in f, and, E(f) the directed arcs of f in its clockwise traversal. If f is unbounded, the respective sum is increased by 16. Of course, the objective is to minimize the total number of bends over all edges, or, equivalently $\min \sum _{(u,v)\in E}\ell _{45}(u,v) + \ell _{90}(u,v) + \ell _{135}(u,v) + r_{45}(u,v)+r_{90}(u,v) + r_{135}(u,v)$.

Now, consider the 5-planar graph of Fig. 5b and observe that each “layer” of this graph consist of six vertices that form an octahedron (solid-drawn), while octahedrons of consecutive layers are connected with three edges (dotted-drawn). Using our ILP formulation, we prove that each octahedron subgraph requires at least 4 bends, when drawn in the octilinear model (except for the innermost one for which we can guarantee only two bends). This implies that $2n/3-2$ bends are required in total to draw the graph of Fig. 5b. For the 6-planar case, we apply our ILP approach to a similar graph consisting of nested octahedrons that are connected by six edges each; see Fig. 5c. This leads to a better lower bound of $4n/3-6$ bends, as each octahedron except for the innermost one requires 8 bends. Summarizing we have the following theorem.

Fig. 5.

Planar graphs of different degrees that require (a) $n/3-1$, (b) $2n/3-2$ and (c) $4n/3-6$ bends.

Theorem 4

There exists a class $G_{n,k}$ of triconnected embedded k-planar graphs, with $4 \le k \le 6$, whose octilinear drawings require at least: (i) $n/3-1$ bends, if $k=4$, (ii) $2n/3-2$ bends, if $k=5$ and (iii) $4n/3-6$ bends, if $k=6$.

5 Conclusions

In this paper, we studied bounds on the total number of bends of octilinear drawings of triconnected planar graphs. We showed how one can adjust an algorithm of Keszegh et al. [14] to derive an upper bound of $4n-10$ bends for general 8-planar graphs. Then, we improved this general bound and previously-known ones for the classes of triconnected 4-, 5- and 6-planar graphs. For these classes of graphs, we also presented corresponding lower bounds.

We mention two major open problems in this context. The first one is to extend our results to biconnected and simply connected graphs and to further tighten the bounds. Since our drawing algorithms might require super-polynomial area (cf. arguments from [2]), the second problem is to study trade-offs between the total number of bends and the required area.