On Smooth Orthogonal and Octilinear Drawings: Relations, Complexity and Kandinsky Drawings

Abstract

We study two variants of the well-known orthogonal graph drawing model: (1) the smooth orthogonal, and (2) the octilinear. Both models are extensions of the orthogonal one, by supporting one additional type of edge segments (circular arcs and diagonal segments, respectively). For planar graphs of maximum vertex degree 4, we analyze relationships between the graph classes that can be drawn bendless in the two models and we also prove $\mathcal {NP}$-hardness for a restricted version of the bendless drawing problem for both models. For planar graphs of higher vertex degree, we present an algorithm that produces bi-monotone smooth orthogonal drawings with at most two segments per edge, which also guarantees a linear number of edges with exactly one segment.

1 Introduction

Orthogonal graph drawing is an intensively studied and well established model for drawing graphs [15, 31]. As a result, several efficient algorithms providing good aesthetics and good readability have been proposed over the years, see e.g., [8, 23, 33, 39]. In such drawings, each vertex corresponds to a point on the Euclidean plane and each edge is drawn as an alternating sequence of axis-aligned line segments; refer to Fig. 1b for an example.

Fig. 1

Different drawings of a planar graph of maximum vertex degree 4: a straight-line, b orthogonal 3-drawing, c smooth orthogonal 2-drawing, and d octilinear 2-drawing

Several research directions build upon this successful model. In this work, we focus on two models that have recently received attention. The first one is the smooth orthogonal [5], in which every edge is a sequence of axis-aligned segments and circular arc segments with common axis-aligned tangents (i.e., quarter, half or three-quarter circular arc segments); refer to Fig. 1c for an example. The second model is the octilinear [3], in which every edge is a sequence of axis-aligned and diagonal (at ${\pm }\, 45^\circ$) segments; refer to Fig. 1d for an example. In the orthogonal and in the smooth orthogonal models, each edge may enter a vertex using one out of four available (axis-aligned) directions, called ports. Thus both models support graphs of maximum vertex degree 4. In the octilinear model, each vertex has eight available ports that are equispaced around each vertex and therefore one can draw graphs of maximum vertex degree 8.

Observe that both models extend the orthogonal by allowing one more type of edge-segments (circular arcs and diagonal segments, respectively). The smooth orthogonal drawing model was introduced with the aim of combining the artistic appeal of Lombardi drawings [18, 21] with the clarity and rigidity of the orthogonal drawings. The octilinear drawing model, on the other hand, is primarily motivated by metro-map and map schematization applications (see, e.g., [28, 35, 36, 38]).

For readability purposes, usually in such drawings one seeks to minimize the edge complexity [15, 31], that is, the maximum number of segments used for representing any edge in the drawing. Also, when the input is a planar graph, one naturally seeks for a corresponding planar drawing. Note that drawings with edge complexity 1 are also called bendless. For simplicity, we refer to drawings with edge complexity k as k-drawings; thus, by definition, orthogonal and octilinear k-drawings have at most $k-1$ bends per edge.

Known Results There exists a plethora of results for each of the aforementioned models; here we overview existing results for drawings with low edge complexity. For a more detailed overview, we point the reader to [40].

• All planar graphs of maximum vertex degree 4, except for the octahedron, admit orthogonal 3-drawings; the octahedron is orthogonal 4-drawable [8, 33]. All planar graphs of maximum vertex degree 3 admit orthogonal 2-drawings [30]. Minimizing the number of bends over all embeddings of a planar graph of maximum vertex degree 4 is $\mathcal {NP}$-hard [26]. For a given planar embedding, however, finding a planar orthogonal drawing with minimum number of bends can be done in polynomial time by an approach, called topology-shape-metrics [39]. The core of this approach is based on min-cost flow computations and works in three phases. Initially, a planar embedding is computed unless specified by the input (topology phase). In the next phase, called shape phase, the angles and the bends of the drawing are computed, yielding an orthogonal representation. In the last phase, called metrics phase, the actual coordinates for the vertices and bends are computed. For more details, we point the reader to [19].

• All planar graphs of maximum vertex degree 4 (including the octahedron) admit smooth orthogonal 2-drawings. Note that not all planar graphs of maximum vertex degree 4 allow for bendless smooth orthogonal drawings [5], and that such drawings may require exponential area [1]. Bendless smooth orthogonal drawings are possible only for subclasses, e.g., for planar graphs of maximum vertex degree 3 [4] and for outerplanar graphs of maximum vertex degree 4 [1]. It is worth mentioning that the complexity of the recognition problem, whether a planar graph of maximum vertex degree 4 admits a bendless smooth orthogonal drawing, has not been settled (it is conjectured to be $\mathcal {NP}$-hard [1]).

• All planar graphs of maximum vertex degree 8 admit octilinear 3-drawings [32], while planar graphs of maximum vertex degree 4 and 5 allow for octilinear 2-drawings in cubic and super-polynomial area, respectively [3]. Bendless octilinear drawings are always possible for planar graphs of maximum vertex degree 3 [17, 29]. Note that deciding whether an embedded planar graph of maximum vertex degree 8 admits a bendless octilinear drawing is $\mathcal {NP}$-hard [35]. It is not, however, known whether this negative result applies for planar graphs of maximum vertex degree 4 or whether these graphs allow for a decision algorithm; in fact, there exist planar graphs of maximum vertex degree 4 that do not admit bendless octilinear drawings [6].

Our Contribution We study smooth orthogonal and octilinear drawings of planar graphs with small edge complexity. Our results are summarized as follows:

• Motivated by the fact that usually one can “easily” convert a smooth orthogonal drawing of a planar graph of maximum vertex degree 4 to a corresponding octilinear one (e.g., by replacing quarter circular arc segments with diagonal edge segments; see Fig. 1c–d for an example), and vice versa, we study in Sect. 3 inclusion-relationships between the graph-classes that admit such drawings. Our findings are also summarized in Fig. 3.

• In Sect. 4, we show that it is $\mathcal {NP}$-hard to decide whether an embedded planar graph of maximum vertex degree 4 admits a bendless smooth orthogonal or a bendless octilinear drawing, in the case where the angles between any two edges incident to a common vertex and the shapes of all edges are specified as part of the input (e.g., as in the last step of the topology-shape-metrics approach [39]). Our proof is a step towards settling the complexities of both decision problems in their general form. Note that, our $\mathcal {NP}$-hardness result shows that the last step of the topology-shape-metrics approach is hard, if considered in isolation in the smooth orthogonal model or in the octilinear model, while in the classic orthogonal model it can be solved efficiently using network flows. This observation suggests that the topology-shape-metrics approach is suitable for neither of the two models.

• Inspired by the Kandinsky model (see, e.g., [7, 14, 23]) for drawing planar graphs of arbitrary vertex degree in an orthogonal style, we present in Sect. 5 two drawing algorithms that yield smooth orthogonal drawings of good quality, that are also bi-monotone, i.e., each edge is drawn xy-monotone. More precisely, the first yields drawings of quadratic area, which can also be transformed into octilinear with bends at $135^\circ$, while maintaining the area consumption asymptotically unchanged. The second algorithm yields drawings of cubic area but at the same time guarantees that at most $2n-5$ edges are drawn with two segments.

Before we proceed with the detailed description of our algorithms, we introduce in Sect. 2 preliminary notions and definitions; for a list of open problems raised by our work refer to Sect. 7.

2 Preliminary Notions and Definitions

Unless otherwise specified, we consider simple undirected graphs. Let $G=(V,E)$ be such a graph. We denote by n and m the number of vertices and edges of G, respectively. We denote by d(v) the vertex degree of a vertex $v \in V$, that is, the number of its incident edges. We say that G has maximum vertex degree$\varDelta$, if G has no vertex with degree larger than $\varDelta$, that is, $d(v) \le \varDelta$ for each $v \in V$.

A drawing$\varGamma$ of G is a function that maps each vertex $v \in V$ to a distinct point $p_v$ in $\mathbb R^2$, and each edge $(u,v)\in E$ to a simple open Jordan curve connecting $p_u$ and $p_v$. Drawing $\varGamma$ is planar if no two edges cross. A graph is planar if it admits a planar drawing. A planar drawing $\varGamma$ of G partitions the plane into topologically connected regions, called faces; the unbounded face is called outerface. A (topological) planar embedding $\mathcal {E}$ of G is an equivalence class of planar drawings that define the same set of faces. Embedding $\mathcal {E}$ can also be defined by the cyclic orders of the edges incident to each vertex (also called combinatorial embedding). For a deeper introduction to graph theoretic basics and to planar graphs, we point the reader to [15, 27].

We assume familiarity with standard graph drawing techniques, such as the canonical ordering [13, 30] and the shift-method by de Fraysseix, Pach and Pollack [13], which we also outline in the following.

The canonical ordering for maximal planar graphs [13] is defined as follows. Let $G=(V,E)$ be a maximal planar graph and let $\pi =(v_1,\ldots ,v_n)$ be a permutation of V. Assume that edges $(v_1,v_2)$, $(v_2,v_n)$ and $(v_1,v_n)$ form a face of G, which we assume w.l.o.g. to be its outerface. For $k=1,\ldots ,n$, let $G_k$ be the subgraph induced by $\cup _{i=1}^k \{v_i\}$ and denote by $C_k$ the outerface of $G_k$. Then, $\pi$ is a canonical ordering of G if for each $k=2,\ldots ,n$ the following hold:

• (i) $G_k$ is biconnected,

• (ii) all neighbors of $v_k$ in $G_{k-1}$ are (consecutive) on $C_{k-1}$, and

• (iii) if $k \ne n$, then $v_k$ has at least one neighbor $v_j$, with $j > k$.

It is known that a canonical ordering of a maximal planar graph can be computed in linear time [30].

The shift-method [13] is a well-known incremental algorithm, which constructs in linear time a planar drawing $\varGamma$ of a maximal planar graph $G=(V,E)$. Drawing $\varGamma$ has integer grid coordinates and requires quadratic area. More precisely, based on a canonical order $\pi$ of G, drawing $\varGamma$ is constructed as follows. Initially, vertices $v_1$, $v_2$ and $v_3$ are placed at points (0, 0), (2, 0) and (1, 1). For $k=4,\ldots ,n$, assume that a planar drawing $\varGamma _{k-1}$ of $G_{k-1}$ has been constructed in which each edge of $C_{k-1}$ is drawn as a straight-line segment with slope $\pm \, 1$, except for the edge $(v_1,v_2)$, which is drawn as a horizontal line segment (contour condition; see Fig. 2a). Also, assume that each of the vertices $v_1,\ldots ,v_{k-1}$ has been associated with a so-called shift-set, which for $v_1$, $v_2$ and $v_3$ are singletons containing only themselves. Let $(w_1,\ldots ,w_p)$ be the vertices of $C_{k-1}$ from left to right in $\varGamma _{k-1}$, where $w_1=v_1$ and $w_p=v_2$. For $i=1,\ldots ,p$, denote by $S(w_i)$ the shift-set of $w_i$. Let $(w_\ell ,\ldots ,w_r)$, with $1 \le \ell < r \le p$ be the neighbors of $v_k$ from left to right along $C_{k-1}$ in $\varGamma _{k-1}$. To avoid edge-overlaps, the algorithm first translates each vertex in $\cup _{i=1}^{\ell } S(w_i)$ one unit to the left and each vertex in $\cup _{i=r}^{p} S(w_i)$ one unit to the right. Then, the algorithm places vertex $v_k$ at the intersection of the line with slope $+1$ through $w_\ell$ with the line with slope $-1$ through $w_r$ and sets the shift-set of $v_k$ to $\{v_k\} \cup _{i=\ell +1}^{r-1}S(w_i)$; see Fig. 2b.

Fig. 2

Illustration of the shift-method by de Fraysseix, Pach and Pollack [13]. a Contour condition. b Placement of $v_k$ in $\varGamma _{k-1}$

3 Relationships Between Graph Classes

In this section, we consider relationships between the classes of graphs that admit smooth orthogonal k-drawings and octilinear k-drawings, where $k \ge 1$. For the sake of simplicity, we denote these two classes by $SC_k$ and $8C_k$, respectively. Our findings are also summarized in Fig. 3.

Fig. 3

Different inclusion-relationships: for $k \ge 1$, $SC_k$ and $8C_k$ correspond to the classes of graphs that admit smooth orthogonal and octilinear k-drawings, respectively

By definition, $SC_1 \subseteq SC_2$ and $8C_1 \subseteq 8C_2 \subseteq 8C_3$ hold. Since each planar graph of maximum vertex degree 8 admits an octilinear 3-drawing [32], class $8C_3$ coincides with the class of planar graphs of maximum vertex degree 8. Similarly, class $SC_2$ coincides with the class of planar graphs of maximum vertex degree 4, because these graphs admit smooth orthogonal 2-drawings [1]. This also implies that $SC_2 \subseteq 8C_2$, since each planar graph of maximum vertex degree 4 admits an octilinear 2-drawing [3]. The relationship $8C_2 \ne 8C_3$ follows from [3], where it was proven that there exist planar graphs of maximum vertex degree 6 that do not admit octilinear 2-drawings. The relationship $SC_2 \ne 8C_2$ follows from [6], where it was shown that there exist planar graphs of maximum vertex degree 5 that admit octilinear 2-drawings and no octilinear 1-drawings, and the fact that planar graphs of maximum vertex degree 5 cannot be drawn in the smooth orthogonal model. The octahedron graph admits neither a bendless smooth orthogonal drawing [5] nor a bendless octilinear drawing [6]. However, since it is of maximum vertex degree 4, it admits 2-drawings in both models [1, 3]. Hence, it belongs to $8C_2 \cap SC_2 \setminus (8C_1 \cup SC_1)$. To prove that $8C_1 \setminus SC_2 \ne \emptyset$, observe that a caterpillar whose spine vertices are of degree 8 clearly admits an octilinear 1-drawing, however, due to its vertex degree it does not admit a smooth orthogonal drawing.

To complete the discussion of the relationships of Fig. 3, we have to show that $SC_1$ and $8C_1$ are incomparable. This is the most interesting part of our proof, since as already mentioned, usually one can “easily” convert a smooth orthogonal drawing of a planar graph of maximum vertex degree 4 to a corresponding octilinear one (e.g., by replacing quarter circular arc segments with diagonal edge segments; see Fig. 1c–d for an example), and vice versa. Since the endpoints of each edge of a bendless smooth orthogonal or octilinear drawing are along a line with slope 0, 1, $-1$ or $\infty$, such conversions are in principle possible. Two difficulties that might arise are to preserve planarity and to guarantee that no two edges enter a vertex using the same port. However, there exist infinitely many (even 4-regular) planar graphs that admit drawings in both models, as we formally prove in the following theorem.

Fig. 4

Illustrations for the proof of Theorem 1 depicting drawings of $G_2$. a A smooth orthogonal 1-drawing. b An octilinear 1-drawing

Theorem 1

There is an infinitely large family of 4-regular planar graphs that admit both bendless smooth orthogonal and bendless octilinear drawings.

Proof

For each $k \in \mathbb {N}_+$ we describe a 4-regular planar graph $G_k=(V_k,E_k)$ with 20k vertices that admits both a bendless smooth orthogonal drawing and a bendless octilinear drawing; refer to Fig. 4 for the case $k=2$. Graph $G_k$ has 4k subgraphs $W_{i,j}$ such that $1 \le i \le 2k$ and $j \in \{t,b\}$, where t and b stand for top and bottom, respectively. Graph $W_{i,j}$ consists of five vertices $c_{i,j}$, $n_{i,j}$, $w_{i,j}$, $e_{i,j}$, and $s_{i,j}$, such that $W_{i,j}$ is a wheel on five vertices, where $c_{i,j}$ is its center-vertex and cycle $C_{i,j}=(n_{i,j},w_{i,j},s_{i,j},e_{i,j})$ is its rim. Vertices $n_{i,j}$, $w_{i,j}$, $s_{i,j}$ and $e_{i,j}$ are the north, west, south and east vertices of $C_{i,j}$, respectively.

All vertices $c_{i,j}$ already have degree four, but every other vertex has degree three. So, in the following, we only describe the edges that will make graph $G_k$ 4-regular. For $1 \le h \le 2k-1$ and $j \in \{t,b\}$, $(e_{h,j},w_{h+1,j}) \in E_k$; dotted edges in Fig. 4. Also, $(w_{1,t},w_{1,b}) \in E_k$ and $(e_{2k,t},e_{2k,b}) \in E_k$; gray edges in Fig. 4. For $1 \le h \le 2k$, $(s_{h,t},n_{h,b}) \in E_k$; dashed edges in Fig. 4. Finally, for $1 \le h \le k$, $(n_{2h-1,t},n_{2h,t}) \in E_k$ and $(s_{2h-1,b},s_{2h,b}) \in E_k$; dashed dotted edges in Fig. 4. With those additional edges, $G_k$ becomes 4-regular. Figure 4 is a certificate that $G_k=(V_k,E_k)$ indeed admits both a bendless smooth orthogonal drawing and a bendless octilinear drawing. $\square$

To complete the discussion of the inclusion relationships of Fig. 3, we show in the next two theorems that $SC_1$ and $8C_1$ are incomparable.

Theorem 2

There are infinitely many 4-regular planar graphs that admit bendless smooth orthogonal drawings but no bendless octilinear drawing.

Proof

Consider the planar graph C of Fig. 5a, which is drawn bendless smooth orthogonal. We claim that C admits no bendless octilinear drawing. If one substitutes its degree-2 vertex (denoted by c in Fig. 5a) by an edge connecting its two neighbors, then the resulting graph is triconnected, which implies that it admits a unique embedding (up to the choice of its outerface; see Fig. 5a–b). Now, observe that the outerface of any octilinear drawing of graph C (if any) has length at most 5 (Constraint 1). In addition, each vertex of this outerface (except for c, which is of degree 2) must have two ports pointing in the interior of this drawing, because every vertex of C is of degree 4, except for c. This implies that the angle formed by any two consecutive edges of this outerface is at most $225^\circ$, except for the pair of edges incident to c (Constraint 2). But if we want to satisfy both constraints, then at least one edge of this outerface must be drawn with a bend; see Fig. 5c. Hence, graph C does not admit a bendless octilinear drawing.

Fig. 5

Illustrations for the proof of Theorem 2

Based on graph C, for each $k \in \mathbb {N}_0$ we construct a 4-regular planar graph $G_k$ consisting of $k + 2$ biconnected components $C_1,\ldots ,C_{k+2}$ arranged in a chain; see Fig. 5d for the case $k=1$. Clearly, graph $G_k$ admits a bendless smooth orthogonal drawing for any k. Since components $C_1$ and $C_{k+2}$ are isomorphic to graph C, graph $G_k$ does not admit a bendless octilinear drawing for any k. $\square$

Theorem 3

There are infinitely many 4-regular planar graphs that admit bendless octilinear drawings but no bendless smooth orthogonal drawing.

Proof

Consider the planar graph B of Fig. 6a, which is drawn bendless in the octilinear model. First, we discuss some structural properties of graph B. Observe that graph B contains a wheel on five vertices as a subgraph, call it $W_5$, which is induced by the vertices drawn as circles in Fig. 6a. Its center is vertex c (gray colored in Fig. 6a) and its rim consists of vertices $w_1$, $w_2$, $w_3$, and $w_4$. Vertices $w_1$ and $w_2$ form a triangular face with vertex $t_1$; analogously, vertices $w_3$ and $w_4$ form a triangular face with $t_2$ (vertices $t_1$ and $t_2$ are drawn as triangles in Fig. 6a). Observe that $t_1$ and $t_2$ form a separation pair and both are connected to vertices $p_1$ and $p_2$ (drawn as pentagons in Fig. 6a) forming two pentagonal faces $(p_1,t_1,w_1,w_4,t_2)$ and $(p_2, t_2, w_3, w_2, t_1)$. Observe that $p_1$ and $p_2$ also form a separation pair and are both connected to vertices $q_1$ and $q_2$ (drawn as squares in Fig. 6a) forming two quadrilateral faces $(q_1, p_2, t_1, p_1)$ and $(q_2,p_1, t_2, p_2)$. Hence, B has two separation pairs and two vertices of degree 2 (that is, $q_1$ and $q_2$). The remaining vertices of B have degree exactly 4.

Fig. 6

Illustrations for the proof of Theorem 3

Fig. 7

All smooth orthogonal drawings a–b of a triangular face, and c, d of a wheel on five vertices, such that all unoccupied ports are on the outerface of the drawing

For each $k \in \mathbb {N}_0$ we construct a 4-regular planar graph $G_k$ consisting of $2k + 4$ copies of B arranged in a cycle; refer to Fig. 6b where each copy of B is drawn as a gray-shaded parallelogram. By construction, graph $G_k$ admits a bendless octilinear drawing, for any k. By planarity, at least one copy of graph B must be embedded with the outerface $(p_1,q_1,p_2,q_2)$ such that each of $q_1$ and $q_2$ has two unoccupied ports incident to this outerface. However, under this restriction the embedding of this particular copy of B must be isomorphic to the one of Fig. 6a. We now proof that, for any k, graph $G_k$ does not admit a bendless smooth orthogonal drawing by showing that graph B does not admit a bendless smooth orthogonal drawing, when its outerface is $(p_1,q_1,p_2,q_2)$ and each of $q_1$ and $q_2$ has two unoccupied ports incident to this outerface.

First, we observe the following: If we want to draw wheel $W_5$, such that all of its unoccupied ports are on its outerface, then none of its four triangular faces must have an unoccupied port pointing in its interior. In the bendless smooth orthogonal model, there are only two possible drawings for a triangular face fulfilling this property (as shown in [1]), which are illustrated in Fig. 7a, b. This implies that $W_5$ admits only two bendless smooth orthogonal drawings such that all of its unoccupied ports are on its outerface, which are illustrated in Fig. 7c, d.

Fig. 8

All smooth orthogonal drawings of the subgraph of graph B induced by wheel $W_5$, and vertices $t_1$ and $t_2$, such that all unoccupied ports are on the outerface of the drawing

Next, we consider vertices $t_1$ and $t_2$. Since each of them defines a triangular face in the subgraph induced by wheel $W_5$, and vertices $t_1$ and $t_2$, we can conclude similar as above, that there are five different drawings of this graph, which are illustrated in Fig. 8. Note that in Fig. 8d, e both $t_1$ and $t_2$ can independently move along the gray colored diagonal rays.

Fig. 9

An enumeration of the candidate positions for $p_1$ and $p_2$ that occur for the cases of: a Fig. 8a, b Fig. 8b, c Fig. 8c, and d Fig. 8d

Fig. 10

An enumeration of the candidate positions for $p_1$ and $p_2$ that occur for the cases of Fig. 8e

In the following, we consider all candidate positions for $p_1$ and $p_2$, which we can identify adopting the following simple rule. In a bendless smooth orthogonal drawing, both endpoints of an edge are located along a horizontal, vertical or diagonal line. Both $p_1$ and $p_2$ are neighbors of both $t_1$ and $t_2$, for which we already defined their locations. If we consider all rays emanating from $t_1$ and $t_2$ with slopes $\{0,1,-1,\infty \}$, then $p_1$ and $p_2$ must be located at an intersection of a ray emanating from $t_1$ and a ray emanating from $t_2$. Following this rule, we enumerate in Figs. 9 and 10 all possible candidate positions for $p_1$ and $p_2$; refer to the gray-colored pentagons. Note that the case illustrated in Fig. 8e has several subcases to be considered depending on the relative positioning of $t_1$ and $t_2$. We illustrate them in Fig. 10a, where we have assumed that the position of one of $t_1$ and $t_2$ is fixed, and then we enumerate how the second one is positioned with respect to the first. Observe that some cases are symmetric with respect to the diagonal line through the center of the wheel (in Fig. 10a, symmetric cases have the same number). In Fig. 10b–e, we illustrate the non-symmetric ones (that are marked with an asterisk in Fig. 10a). More precisely, Fig. 10b illustrates the case where $t_1$ and $t_2$ are diagonally aligned; Fig. 10c illustrates the case where $t_1$ and $t_2$ are vertically aligned (which is symmetric to the case where they are horizontally aligned); Figs 10d, e illustrate the remaining two cases of Fig. 10a.

Table 1 An overview of the forbidden patterns (FP) occurring when placing $p_1$ and $p_2$ at each of the candidate positions as they are enumerated in Figs. 9 and 10; the gray-colored cell of this table illustrates the forbidden patterns occurring when placing $q_1$ and $q_2$ at each of the candidate positions of Fig. 11, which illustrates the only valid drawing derived by placing $p_1$ and $p_2$ at positions 2 and 6 of Fig. 9a

For each candidate position, we then try to draw the edges from $t_1$ and $t_2$ to $p_1$ and $p_2$ using one of the edge segments supported by the smooth orthogonal model. The resulting drawing is valid if and only if none of the following forbidden patterns appears:

• FP.I. an edge is involved in crossings (as planarity is deviated),

• FP.II. a port of a vertex is used twice (as this is not permitted by our model),

• FP.III. a vertex has an unoccupied port not incident to the outerface (as this will not allow adding $q_1$ or $q_2$).

Otherwise, the resulting drawing is invalid. Note that in Figs. 9d and 10 we have appropriately chosen the radii of the arcs incident to $t_1$ and $t_2$, so to avoid a position for $p_1$ and $p_2$ to become invalid due to Forbidden Pattern I.

For each candidate position as it is enumerated in each subfigure of Figs. 9 and 10, we demonstrate in Table 1 whether it leads to some forbidden pattern. It is immediate to see from Table 1 that all candidate positions for placing $p_1$ and $p_2$ that are obtained from the cases illustrated in Figs. 9c–d and b–e yield Forbidden Pattern I, II or III, except for Position 4 of Fig. 9c, Position 5 of Fig. 10b and Position 4 of Fig. 10c. These particular positions do not yield any forbidden pattern. However, since we have to place two vertices (namely, $p_1$ and $p_2$), only one of them can be placed without introducing a forbidden pattern; the other will inevitably introduce one.

Fig. 11

An enumeration of the candidate positions for placing $q_1$ and $q_2$, when $p_1$ and $p_2$ have been placed at positions 2 and 6 of Fig. 9a, respectively

It remains to discuss the candidate positions for placing $p_1$ and $p_2$ that are obtained from the cases illustrated in Fig. 9a, b. As demonstrated in Table 1, the former has two candidate positions (namely, Positions 2 and 6), which do not yield any forbidden pattern; the latter case has three such candidate positions (namely, Positions 3, 7 and 8). We consider the latter case first. By combining the three candidate positions for both $p_1$ and $p_2$, we can conclude that there exist in total three different placement combinations for $p_1$ and $p_2$. However, it is not difficult to see that all three of them yield Forbidden Pattern II. Regarding the former case, we observe that by placing $p_1$ and $p_2$ at Positions 2 and 6 of Fig. 9a, respectively (which are the only ones not introducing any forbidden pattern), we obtain a valid drawing. This drawing is illustrated in Fig. 11.

We proceed by considering all possible candidate positions for placing $q_1$ and $q_2$, as we did for $p_1$ and $p_2$; refer to the gray-colored squares in Fig. 11 for an enumeration of all cases. Note that in Fig. 11 we have appropriately chosen the radii of the arcs incident to $p_1$ and $p_2$, so to avoid a position for $q_1$ and $q_2$ to become invalid due to Forbidden Pattern I. In the last (shaded in gray) row of Table 1, we demonstrate that each candidate position for placing $q_1$ and $q_2$ yields either Forbidden Pattern I or III. As a result, we can conclude that neither $q_1$ nor $q_2$ can be added to the only valid drawing for $p_1$ and $p_2$ of Fig. 11, which completes the proof of this theorem. $\square$

4 $\mathcal {NP}$-Hardness Results

In this section, we study the complexity of the bendless smooth orthogonal and octilinear drawing problems. As a first step towards addressing the complexity of both problems for planar graphs of maximum vertex degree 4 in general, here we make an additional assumption. We assume that the input, apart from an embedding, also specifies a smooth orthogonal or an octilinear representation, which are defined analogously to the orthogonal ones: (i) the angles between consecutive edges incident to a common vertex in the cyclic order around it (given by the planar embedding) are specified, and (ii) the shape of each edge (e.g., straight-line, or quarter circular arc) is also specified. In other words, we assume that our input is analogous to the one of the last step of the topology-shape-metrics approach. We first present our reduction for the smooth orthogonal drawing model and afterwards we describe the required modifications for the corresponding reduction for the octilinear model.

Theorem 4

Given a planar graph G of maximum vertex degree 4 and a smooth orthogonal representation $\mathcal {R}$, it is $\mathcal {NP}$-hard to decide whether G admits a bendless smooth orthogonal drawing preserving $\mathcal {R}$. This holds even if $\mathcal {R}$ requires all edges to be drawn as straight-line segments or quarter circular arcs.

Proof

Our reduction is from the well-known 3-SAT problem [25]. Given a 3-SAT formula $\varphi$ in conjunctive normal form, we construct a graph $G_\varphi$ and a smooth orthogonal representation $\mathcal {R}_\varphi$, such that $G_\varphi$ admits a bendless smooth orthogonal drawing $\varGamma _\varphi$ preserving $\mathcal {R}_\varphi$ if and only if formula $\varphi$ is satisfiable; see also Fig. 12.

The main ideas of our construction are: (i) specific straight-line edges in $\varGamma _\varphi$ transport information encoded in their length, (ii) rectangular faces of $\varGamma _\varphi$ propagate the edge length of one side to its opposite side, and (iii) for a face composed of two straight-line edges and a quarter circular arc, the straight-line edges are of same length, which allows us to change the direction in which the information “flows”.

Fig. 12

Drawing $\varGamma _\varphi$ for $\varphi = (a \vee b \vee c) \wedge (\overline{a} \vee \overline{b} \vee c)$ and the assignment $a = \texttt {false}$ and $b = c = \texttt {true}$

Variable Gadget For each variable x of $\varphi$, we introduce a gadget, which is illustrated in Fig. 13. The bold-drawn quarter circular arc ensures that the sum of the edge lengths to its left is the same as the sum of the edge lengths to its bottom (refer to the edges with gray endvertices). As “input” the gadget gets three edges of unit length $\ell (u)$. This ensures that $\ell (x) + \ell (\overline{x}) = 3 \cdot \ell (u)$ holds for the “output literals” x and $\overline{x}$, where $\ell (x)$ and $\ell (\overline{x})$ denote the lengths of two edges representing x and $\overline{x}$.

Fig. 13

The variable gadget; gray-colored arrows show the information “flow”. a True state: $\ell (x)=2$, $\ell (\overline{x})=1$. b False state: $\ell (x)=1$, $\ell (\overline{x})=2$

To introduce our concept, assume that the lengths of all straight-line edges are integral and at least 1. If we could require $\ell (u) = 1$, then $\ell (x), \ell (\overline{x}) \in \{1,2\}$. This would allow us to encode the assignment $x=\mathtt {true}$ with $\ell (x) = 2$ and $\ell (\overline{x}) = 1$, and the assignment $x=\mathtt {false}$ with $\ell (x) = 1$ and $\ell (\overline{x}) = 2$ (i.e., a length of 2 implies that the literal is true). However, if we cannot avoid, e.g., that $\ell (u) = 2$, then the variable gadget would not prevent us from setting $\ell (x) = \ell (\overline{x}) = 3$, which means that x and $\overline{x}$ are “half-true”. We solve this issue by introducing the so-called parity gadget, that allows us to relax the integer constraint and to ensure that $\ell (x), \ell (\overline{x}) \in \{\ell (u) + \varepsilon ,~2 \ell (u) - \varepsilon \}$, for $\varepsilon<< \ell (u)$.

Parity Gadget For each variable x of $\varphi$, graph $G_\varphi$ has a gadget, which results in overlaps in $\varGamma _\varphi$, if the values of $\ell (x)$ and $\ell (\overline{x})$ do not differ significantly. For an illustration, refer to Fig. 14. The central part of this gadget is a “vertical gap” of width $3 \cdot \ell (u)$ (shaded in gray in Fig. 14a–c) with two blocks of vertices (triangular- and square-shaped in Fig. 14b–c) pointing inside the gap; a more detailed illustration of the vertical gap is given in Fig. 14c. Each block defines two square-shaped faces and three triangular faces, each formed by two straight-line edges and a quarter circular arc. Depending on the choice of $\ell (x)$ and $\ell (\overline{x})$, one of the blocks may be located above the other. If $\ell (x) \approx \ell (\overline{x})$, however, the two blocks are not far enough apart from each other leading to overlaps; see Fig. 14c.

Fig. 14

The parity gadget; gray-colored arrows show the information “flow”. a$x=\mathtt {true}$. b$x=\mathtt {false}$. c$\ell (x) \approx \ell (\overline{x})$. d Detail

Consider the case where $x = \texttt {false}$. The case where $x = \texttt {true}$ is symmetric. If $x = \texttt {false}$, we have to ensure that the two quarter circular arcs that are intersected by the dashed diagonal line-segment of Fig. 14d do not introduce crossings, i.e., in other words the top one should be located on top of the bottom one in Fig. 14d. Since we know that both of these arcs have radius $\ell (u)$, their centers (gray-colored in Fig. 14d) should be at a distance greater than $2 \cdot \ell (u)$ apart from each other, i.e., the length of the dashed diagonal line segment is at least $2 \cdot \ell (u)$. However, the length of this segment can be easily expressed in dependence of $\lambda = \ell (\overline{x}) - \ell (x)$ as follows: $\sqrt{4 \lambda ^2 + \ell (u)^2}$. Hence, in order to avoid crossings it is not difficult to see that $\lambda > \sqrt{3}/{2}\cdot \ell (u) \approx 0.866 \cdot \ell (u)$. This implies that $\ell (x), \ell (\overline{x}) \in (0,~1.067 \cdot \ell (u)) \cup (1.933 \cdot \ell (u),~3)$, i.e., $\varepsilon < 0.067 \cdot \ell (u)$ to avoid crossings.

Clause Gadget For each clause of $\varphi$ with literals a, b and c, we introduce a gadget, which is illustrated in Fig. 15a. The bold-drawn quarter circular arc of Fig. 15a compares two sums of information. From the righthand side, four edges of unit length “enter” the arc. Observe that there is also a free edge (marked with an asterisk in Fig. 15a), which also contributes to the sum. Hence, the sum of edge lengths on the righthand side of this arc is greater than $4 \cdot \ell (u)$, since the free edge must have non-zero length. The three literals “enter” at the bottom; the sum here is $\ell (a) + \ell (b) + \ell (c)$. Combining both, we obtain that $\ell (a) + \ell (b) + \ell (c) > 4 \cdot \ell (u)$ must hold. The bold-drawn quarter circular arc of Fig. 15a implies that the length of the free edge must be equal to the difference between the two sides of this inequality. Also, note that not all a, b and c can be $\texttt {false}$, since in this case $\ell (a) + \ell (b) + \ell (c) = 3 \cdot (\ell (u)+\varepsilon ) < 4 \cdot \ell (u)$, because $\varepsilon<< \ell (u)$. However, if at least one literal is $\texttt {true}$, then $\ell (a) + \ell (b) + \ell (c) \ge 4 \cdot \ell (u) + \varepsilon$ and our inequality holds.

Fig. 15

Different gadgets; gray-colored arrows show the information “flow”. a Clause gadget. b Crossing gadget. c Copy gadget

Auxiliary Gadgets The crossing gadget just consists of a rectangle and is used to allow two flows of information to cross each other; see Fig. 15b. The copy gadget takes an information and creates three copies of this information; see Fig. 15c. This is because the vertices of each gray colored quadrilateral face in Fig. 15c must be located at the corners of a rectangle whose sides have slopes $\pm \, 1$, which implies that its opposite sides must be of the same length. Finally, the unit length gadget is a single edge, which we assume to have length $\ell (u)$. In Fig. 12, the unit length gadget is marked with an asterisk.

Description of the Construction We now describe our construction; see Fig. 12. Graph $G_\varphi$ contains one unit length gadget, which is copied $O(\nu +\mu )$ times using the copy gadget, where $\nu$ and $\mu$ denote the number of variables and clauses of $\varphi$, respectively (since each variable and each clause introduces six and two copies of the copy gadget, respectively). For each variable of $\varphi$, graph $G_\varphi$ has a variable gadget and a parity gadget, each of which is connected to different copies of the unit length gadget. For each clause of $\varphi$, graph $G_\varphi$ has a clause gadget, which has four connections to different copies of the unit length gadget. We compute $\mathcal {R}_\varphi$ as follows. We place the variable gadget of each variable x above and to the left of its parity gadget and we connect the output literals of the variable gadget of x with its parity gadget through a copy gadget. We place the variable and the parity gadgets of the i-th variable below and to the right of the corresponding ones of the $(i-1)$-th variable. We place each clause gadget to the right of the sketch constructed so far, so that the gadget of the i-th clause is to the right of the $(i-1)$-th clause. This allows us to connect copies of the output literals of the variable gadget of each variable with the clause gadgets that contain it, so that all possible crossings (which are resolved using the crossing gadget) appear above the clause gadgets. More precisely, if a clause contains a literal of the i-th variable, we have a crossing with the literals of all variables with indices $(i+1)$ to $\nu$. Hence, for each clause we add $O(\nu )$ crossing and three copy gadgets. Note that all copy gadgets of the unit length gadget lie below all variable, parity, and clause gadgets. The obtained representation $\mathcal {R}_\varphi$ conforms with the one of Fig. 12. Since the order of the variable and clause gadgets can be arbitrarily chosen in advance, we can assume that their connections are fixed, which implies that we know in advance the number and the positions of the required copy and crossing gadgets. Since, as already mentioned, for each clause we add $O(\nu )$ crossing gadgets, the construction can be done in $O(\nu \mu )$ time.

To complete the proof, assume that graph $G_\varphi$ admits a bendless smooth orthogonal drawing $\varGamma _\varphi$ preserving $\mathcal {R}_\varphi$. We compute a truth assignment for $\varphi$ as follows. For each variable x of $\varphi$, we set x to $\texttt {true}$ if and only if $\ell (x) \ge 1.933 \cdot \ell (u)$. Since for each clause $(a \vee b \vee c)$ of $\varphi$ we have that $\ell (a) + \ell (b) + \ell (c) > 4 \cdot \ell (u)$, it follows that at least one of a, b and c must be $\texttt {true}$. Hence, $\varphi$ admits a truth assignment. For the opposite direction, based on a truth assignment of $\varphi$, we can set, e.g., $\ell (x)=1.95$ and $\ell (\overline{x})=1.05$ for each variable x, assuming that $\ell (u)=1$. Then, arranging the variable and the clause gadgets of $G_\varphi$ as in Fig. 12 yields a bendless smooth orthogonal drawing $\varGamma _\varphi$ preserving $\mathcal {R}_\varphi$. $\square$

Remark 1

The special case of our problem, in which circular arcs are not present, is closely related to the so-called HV-rectilinear planarity testing [34]. In this problem, each edge has either an H- or a V-label and the goal is to determine whether there exist a rectilinear drawing in which all edges with an H-label are drawn as horizontal segments, while all edges with an V-label are drawn as vertical segments. As opposed to our problem, HV-rectilinear planarity testing is polynomial-time solvable in the fixed embedding setting [20] (note that the angles around each vertex are not specified as part of the input of the problem) and becomes $\mathcal {NP}$-hard in the variable embedding setting [16].

We now proceed to prove the analogous of Theorem 4 for the octilinear model.

Fig. 16

The parity gadget for the octilinear model

Theorem 5

Given a planar graph G of maximum vertex degree 4 and an octilinear representation $\mathcal {R}$, it is $\mathcal {NP}$-hard to decide whether G admits a bendless octilinear drawing preserving $\mathcal {R}$.

Proof

In principle, our proof follows the same reduction scheme as the one of Theorem 4. More precisely, we can adjust to the octilinear model by replacing quarter circular arcs with diagonal segments. By doing so, we maintain planarity (by construction). However, the parity gadget has to be adjusted properly, so to maintain its functionality. To this end, we only change the vertical gap of parity gadget as in Fig. 16, which shows the case where $x = \texttt {false}$; the case where $x = \texttt {true}$ is symmetric.

It is not difficult to see that the smallest vertical distance d between the blocks in the vertical gap (illustrated as a dotted line-segment in Fig. 16) equals to $6\ell (\overline{x}) - 6\ell (x) - 5 \ell (u)$, which implies $\ell (\overline{x}) - \ell (x) > 5/6 \cdot \ell (u)$, since d must be strictly greater than zero. Thus, $\varepsilon< 0.084 \cdot \ell (u)<< \ell (u)$. $\square$

5 Bi-Monotone Drawings

In this section, we study variants of the Kandinsky drawing model [7, 14, 23], which forms an extension of the orthogonal model to graphs of vertex degree greater than 4. In this model, the vertices are represented as squares, placed on a coarse grid with multiple edges attached to each side of them aligned on a finer grid. Since Kandinsky drawings find applications in diverse areas, such as VLSI design, UML diagrams and business process modeling, this drawing model has been extensively studied over the years; see, e.g., [9, 10].

The Kandinsky model allows for natural extensions to both smooth orthogonal and octilinear models. We are aware of only one preliminary result in this direction for the former model: A linear time drawing algorithm is presented in [5] for the production of smooth orthogonal 2-drawings for planar graphs of arbitrary vertex degree in quadratic area, in which all vertices are on a line $\ell$ and the edges are drawn either as half circles (above or below $\ell$), or as two consecutive half circles one above and one below $\ell$ (that is, the latter ones are of complexity 2, but they are at most $\lfloor (n-3)/2 \rfloor$ [11]).

For an input maximal planar graph G (of arbitrary vertex degree), our goal is to construct a smooth orthogonal (or an octilinear) 2-drawing for G with the following aesthetic benefits over the aforementioned drawing algorithm:

• (i) the vertices are not restricted along a line, and

• (ii) each edge is bi-monotone [24], i.e., xy-monotone.

We achieve our goal at the cost of slightly more edges drawn with complexity 2 or at the cost of increased drawing area (but still polynomial).

Our first approach is a modification of the shift-method [13] (see also Sect. 2). Based on a canonical order $\pi =(v_1,\ldots ,v_n)$ of G, we construct a planar smooth orthogonal 2-drawing $\varGamma$ of G in the Kandinsky model, as follows. We place $v_1$, $v_2$ and $v_3$ at points (0, 0), (2, 0) and (1, 1), respectively. Hence, we can draw edge $(v_1,v_2)$ as a horizontal line-segment, and each of edges $(v_1,v_3)$ and $(v_2,v_3)$ as a quarter circular arc. We also color edge $(v_1,v_3)$ blue and edge $(v_2,v_3)$ green; edges of the same color will eventually be drawn in the same manner. For $k=4,\ldots ,n$, assume that a smooth orthogonal 2-drawing $\varGamma _{k-1}$ of the subgraph $G_{k-1}$ of G induced by $v_1,\ldots ,v_{k-1}$ has been constructed, in which each edge of the outerface $C_{k-1}$ of $\varGamma _{k-1}$ is drawn as a quarter circular arc, whose endvertices are on a line with slope $\pm \, 1$, except for edge $(v_1,v_2)$, which is drawn as a horizontal segment (called contour condition in the shift-method). For an illustration, refer to Fig. 17a. Each of $v_1,\ldots ,v_{k-1}$ is also associated with a so-called shift-set, which for $v_1$, $v_2$ and $v_3$ are singletons containing only themselves (as in the shift-method).

Fig. 17

Illustration of the modified shift-method for the smooth orthogonal model. a Contour condition. b Placement of $v_k$ in $\varGamma _{k-1}$

Let $(w_1,\ldots ,w_p)$ be the vertices of $C_{k-1}$ from left to right in $\varGamma _{k-1}$, where $w_1=v_1$ and $w_p=v_2$. Let $(w_\ell ,\ldots ,w_r)$, $1 \le \ell < r \le p$, be the neighbors of $v_k$ from left to right along $C_{k-1}$ in $\varGamma _{k-1}$. As in the shift-method, our algorithm first translates each vertex in $\cup _{i=1}^{\ell } S(w_i)$ one unit to the left and each vertex in $\cup _{i=r}^{p} S(w_i)$ one unit to the right, where S(v) is the shift-set of $v \in V$. During this translation, each of edges $(w_{\ell },w_{\ell +1})$ and $(w_{r-1},w_r)$ acquires a horizontal segment (see the bold edges of Fig. 17b). We place vertex $v_k$ at the intersection of line $\lambda _\ell$ with slope $+1$ through $w_\ell$ with line $\lambda _r$ with slope $-1$ through $w_r$ (which are drawn dotted in Fig. 17b) and we set the shift-set of $v_k$ to $\{v_k\} \cup _{i=\ell +1}^{r-1}S(w_i)$, as in the shift-method. We draw each of edges $(w_\ell ,v_k)$ and $(v_k,w_r)$ as a quarter circular arc. The remaining edges incident to $v_k$ are drawn with complexity 2. More precisely, for $i=\ell +1,\ldots ,r-1$, edge $(w_i,v_k)$ has a vertical line-segment that starts from $w_i$ and ends either at $\lambda _\ell$ or $\lambda _r$ and a quarter circular arc from the end of the previous segment to $v_k$. Hence, the contour condition is satisfied.

We color edge $(w_\ell ,v_k)$ blue, edge $(v_k,w_r)$ green and the remaining edges incident to $v_k$ in $G_k$ red (this type of coloring is also known as Schnyder coloring [22, 37]). Observe that each blue and green edge consists of a quarter circular arc and a horizontal segment (that may have zero length), while a red edge consists of a vertical segment and a quarter circular arc (that may have zero radius). We are now ready to state the following theorem.

Theorem 6

A maximal planar n-vertex graph admits a bi-monotone planar smooth orthogonal 2-drawing in the Kandinsky model, which requires $O(n^2)$ area and can be computed in O(n) time.

Proof

Bi-monotonicity and the fact that the computed drawing is a 2-drawing follows by construction. The time complexity follows from [12]. Planarity is proven by induction. Drawing $\varGamma _3$ is planar by construction. Assuming that $\varGamma _{k-1}$ is planar, we observe that no two edges incident to $v_k$ cross in $\varGamma _k$. Also, these edges do not cross edges of $\varGamma _{k-1}$. Since the radii of the arcs of the edges incident to vertices that are shifted remain unchanged and since edges incident to vertices in the shift-sets retain their shape, drawing $\varGamma _k$ is planar. This completes our proof. $\square$

For the octilinear model, we can analogously state the following theorem.

Theorem 7

A maximal planar n-vertex graph admits a bi-monotone planar octilinear 2-drawing in the Kandinsky model, which requires $O(n^2)$ area and can be computed in O(n) time. Additionally, each bend is at $135^\circ$.

Proof

We can convert the layout computed for the smooth orthogonal model to octilinear by redrawing all its quarter circular arcs to diagonal segments; see also Fig. 18b. This results in bends at $135^\circ$. Planarity follows from the fact that blue and green edges do not pass through vertices by construction. $\square$

Fig. 18

Illustration of the modified shift-method for the octilinear model. a Contour condition. b Placement of $v_k$ in $\varGamma _{k-1}$

We reduce the number of edges drawn with complexity 2, by computing new y-coordinates for the vertices, while keeping their x-coordinates unchanged. To achieve this, we process the vertices of G in the same canonical ordering $\pi = (v_1,\ldots ,v_n)$ maintaining the following invariant (which is a modification of the contour condition):

• (I.1) Each edge of the outerface has a quarter circular arc segment of non-zero radius, except for the edge $(v_1,v_2)$; see Fig. 19a.

Initially, we set $y(v_1) = y(v_2) = 0$. For $k=3,\ldots ,n$, we assume as in the shift-method that the neighbors of vertex $v_k$ in $\varGamma _{k-1}$ are $(w_\ell ,\ldots ,w_r)$ from left to right along $C_{k-1}$. Next, from each of the vertices $w_\ell ,\ldots ,w_r$ that are strictly to the left (right) of $v_k$, we draw a line with slope $+1$ ($-1$, resp.); refer to the dashed drawn lines of Fig. 19b. The intersections of these lines with the vertical line $L_k:x=x(v_k)$ are candidate positions for the placement of $v_k$. If there is a vertex $w_i$, for some $i=\ell ,\ldots ,r$, whose x-coordinate is equal to the x-coordinate of vertex $v_k$ (that is, $x(w_i)=x(v_k)$), then there is one more candidate position, called trivial, for the placement of $v_k$, which is also along the line $L_k$ at $(x(w_i), y(w_i)+1)$; refer to the candidate position marked with an asterisk in Fig. 19b. We choose to place $v_k$ at the highest candidate position. More precisely, let $\varDelta _x(u, v)$ be the horizontal distance between vertices u and v. Then, formally, the y-coordinate of vertex $v_k$ is computed as follows:

$$\begin{aligned} y(v_k) = \max _{w\in \{w_\ell ,\ldots ,w_r\}}\{y(w) + \max \{\varDelta _x(v_k, w),1\} \} \end{aligned}$$

(1)

Let $w^*\in \{w_\ell ,\ldots ,w_r\}$ be the vertex of $C_{k-1}$ defining the highest candidate position. Note that, in general, more than one vertex may define the highest candidate position. It is not difficult to see that edge $(v_k,w^*)$ can be drawn as a quarter circular arc, unless $v_k$ is placed in the trivial candidate position, in which case we draw it as a vertical line-segment of unit length. This immediately implies that (at least) $n-1$ edges are drawn with complexity 1, as desired. We draw the remaining edges incident to $v_k$ with complexity 2. More precisely, each of these edges is composed of two segments; one quarter circular arc segment incident to $v_k$ followed by a vertical line-segment incident to the other endpoint. Since $x(w_\ell )< x(v_k) < x(w_r)$, it follows that Invariant 1 is maintained, by construction; in addition, note that the quarter circular arc of Invariant 1 is always incident to vertex $v_k$. We are now ready to state the following theorem.

Fig. 19

Illustration of the contour condition and placement of $v_k$ in $\varGamma _{k-1}$. a Invariant 1. b Placement of $v_k$ in $\varGamma _{k-1}$

Theorem 8

A maximal planar n-vertex graph G admits a bi-monotone planar smooth orthogonal 2-drawing $\varGamma$ with at least $n-1$ edges drawn with complexity 1 in the Kandinsky model, which requires $O(n^3)$ area and can be computed in O(n) time.

Proof

The time complexity follows from the shift-method. Since the fact that at least $n-1$ edges are drawn with complexity 1 has already been discussed, in order to prove this theorem, it remains to show that the computed drawing is planar and that its area is cubic. The latter can be proven immediately. Since the horizontal distance between any two vertices of G in $\varGamma$ is O(n), it follows that the vertical distance between any two consecutive (in the canonical ordering) vertices in $\varGamma$ cannot be more than O(n), which implies that the height of $\varGamma$ is at most $O(n^2)$. Hence, the area occupied by $\varGamma$ is $O(n^3)$.

We prove planarity inductively. For the base of the induction, note that drawing $\varGamma _3$ is planar. Assuming that $\varGamma _{k-1}$ is planar, we show in the following that $\varGamma _k$ is planar, as well. By construction, the edges that are incident to $v_k$ do not cross each other. This is because of Invariant 1, which ensures that no two neighbors of $v_k$ in $G_k$ have the same x-coordinate. Since drawing $\varGamma _{k-1}$ remains unchanged after placing $v_k$ (and hence planar as subdrawing of $\varGamma _k$), it remains to prove that the edges incident to $v_k$ do not introduce crossings with edges of $\varGamma _{k-1}$; in particular with edges of $C_{k-1}$.

Fig. 20

Illustration for the proof of Theorem 8

Let $L_\ell$ and $L_r$ be the vertical lines through $w_\ell$ and $w_r$ in $\varGamma _k$, respectively; see Fig. 20. By construction, there is no vertex in the region $R_\ell$ between $L_\ell$ and $L_k$ that lies above the line $\lambda _\ell$ with slope $+1$ through $v_k$. Symmetrically, there is no vertex in the region $R_r$ between $L_k$ and $L_r$ that lies above the line $\lambda _r$ with slope $-1$ through $v_k$; both regions $R_\ell$ and $R_r$ are highlighted in gray in Fig. 20. However, along the parts of $\lambda _\ell$ and $\lambda _r$ that lie in the interior of $R_\ell$ and $R_r$, respectively, there might exist several vertices (one of them is $w^*$).

Since $w_\ell$ and $w_r$ are the leftmost and rightmost neighbors of $v_k$ in $\varGamma _{k-1}$, it follows that the neighbors $w_\ell ,\ldots ,w_r$ of $v_k$ in $G_k$ lie between $L_\ell$ and $L_r$ (and either completely below or along $\lambda _\ell$ and $\lambda _r$). Each edge incident to $v_k$ in $G_k$ has a circular arc segment that starts from $v_k$ and ends at a point along $\lambda _\ell$ or $\lambda _r$ (followed by a vertical segment of possibly zero length towards one of $w_\ell ,\ldots ,w_r$), such that no two such circular arc segments overlap, as by Invariant 1 no two vertices among $w_\ell ,\ldots ,w_r$ have the same x-coordinate. Since in regions $R_\ell$ and $R_r$ there are no vertices of $G_k$, it follows that these circular arcs may only cross other circular arc segments that lie in $R_\ell$ and $R_r$, which must have both endpoints either along $\lambda _\ell$ or along $\lambda _r$. However, such crossings are not possible because the radius of the circular arc segment of an edge $(w_i,w_{i+1})$ of $C_{k-1}$ is smaller than the radius of the circular arc segments of both edges $(v_k,w_i)$ and $(v_k,w_{i+1})$ in such a scenario; refer to the dotted drawn edges of Fig. 20. Since the vertical edge segments incident to each of $w_\ell ,\ldots ,w_r$ neither cross each other nor cross edges of $C_{k-1}$, it follows that $\varGamma _k$ is in fact planar. $\square$

6 Example Run of our Drawing Algorithm

In this section, we describe an example run of our drawing algorithm from Sect. 5 on a planar triangulation on seven vertices. Figure 21 shows the steps of constructing a smooth orthogonal drawing of this graph using our modification of the shift-method.

Fig. 21

The steps of drawing a planar graph with our modified shift-method

Figure 22 illustrates how new y-coordinates are assigned to the vertices so to reduce the number of edges drawn with complexity 2 (observe that the x-coordinates are the ones of Fig. 21e). In particular, Fig. 22a shows how this is done for the first three vertices. Figure 22b–e illustrate how the fourth, the fifth, the sixth and the seventh vertex of the graph is added. The bold edges in each subfigure of Fig. 22 are the ones defining the y-coordinate which are drawn with complexity 1 at each step of the canonical order. The final drawing is the one of Fig. 22e. We emphasize on the additional area consumption, which on the vertical dimension increases to quadratic.

Fig. 22

Illustration of the reduction of the number of edges drawn with complexity 2

7 Conclusions

In this paper, we continued the study of smooth orthogonal and octilinear drawings. Our $\mathcal {NP}$-hardness proofs are a first step towards settling the complexity of both drawing problems. It is interesting to study whether any of the two problems also belongs to $\mathcal {NP}$. We further conjecture that deciding whether a planar graph admits a bendless smooth orthogonal drawing is $\mathcal {NP}$-hard, even in the case where only the planar embedding is specified by the input. For the octilinear drawing problem, it is of interest to know if it remains $\mathcal {NP}$-hard even for planar graphs of maximum vertex degree 4 or if these graphs allow for a decision algorithm. Our drawing algorithms guarantee bi-monotone 2-drawings with a certain number of complexity-1 edges for maximal planar graphs. Improvements or generalizations to non-triangulated planar graphs are of importance.