Non-aligned Drawings of Planar Graphs

Abstract

A non-aligned drawing of a graph is a drawing where no two vertices are in the same row or column. Auber et al. showed that not all planar graphs have a non-aligned planar straight-line drawing in the $n\times n$-grid. They also showed that such a drawing exists if up to $n-3$ edges may have a bend.

In this paper, we give algorithms for non-aligned planar drawings that improve on the results by Auber et al. In particular, we give such drawings in an $n\times n$-grid with at most $\frac{2n-5}{3}$ bends, and we study what grid-size can be achieved if we insist on having straight-line drawings.

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 Introduction

At last year’s GD conference, Auber et al. [2] introduced the concept of rook-drawings: these are drawings of a graph in an $n\times n$-grid such that no two vertices are in the same row or the same column (thus, if the vertices were rooks on a chessboard, then no vertex could beat any other). They showed that not all planar graphs have a planar straight-line rook-drawing, and then gave a construction of planar rook-drawings with at most $n-3$ bends. From now on, all drawings are required to be planar.

In this paper, we continue the study of rook-drawings. Note that if a graph has no straight-line rook-drawing, then we can relax the restrictions in two possible ways. We could either, as Auber et al. did, allow to use bends for some of the edges, and try to keep the number of bends small. Or we could increase the grid-size and ask what size of grid can be achieved for straight-line drawings in which no two vertices share a row or a column; this type of drawing is known as non-aligned drawing [1]. A rook-drawing is then a non-aligned drawing on an $n \times n$-grid.

Existing Results: Apart from the paper by Auber et al., non-aligned drawings have arisen in a few other contexts. Alamdari and Biedl showed that every graph that has an inner rectangular drawing also has a non-aligned drawing [1]. These drawings are so-called rectangle-of-influence drawings and can hence be assumed to be in an $n\times n$-grid. In particular, every 4-connected planar graph with at most $3n-7$ edges therefore has a rook-drawing (see Sect. 3.1 for details). Non-aligned drawings were also created by Di Giacomo et al. [9] in the context of upward-rightward drawings. They showed that every planar graph has a non-aligned drawing in an $O(n^4)\times O(n^4)$-grid. Finally, there have been studies about drawing graphs with the opposite goal, namely, creating as many collinear vertices as possible [15].

Our Results: In this paper, we show the following (the bounds listed here are upper bounds; see the sections for tighter bounds):

• Every planar graph has a non-aligned straight-line drawing in an $n^2\times n^2$-grid. This is achieved by taking any weak barycentric representation (for example, the one by Schnyder [16]), scaling it by a big enough factor, and then moving vertices slightly so that they have distinct coordinates while maintaining a weak barycentric representation.

• Every planar graph has a non-aligned straight-line drawing in an $n\times \frac{1}{2}n^3$-grid. This is achieved by creating drawings with the canonical ordering [11] in a standard fashion (similar to [8]). However, we pre-compute all the x-coordinates (and in particular, make them a permutation of $\{1,\dots ,n\}$), and then argue that with the standard construction the slopes do not get too big, and hence the height is quadratic. Modifying the construction a bit, we can also achieve that all y-coordinates are distinct and that the height is cubic.

• Every planar graph has a rook-drawing with at most $\frac{2n-5}{3}$ bends. This is achieved via creating a so-called rectangle-of-influence drawing of a modification of G, and arguing that each modification can be undone while adding only one bend.

Our bounds are even better for 4-connected planar graphs. In particular, every 4-connected planar graph has a rook-drawing with at most 1 bend (and more generally, the number of bends is no more than the number of so-called filled triangles). We also show that any so-called nested-triangle graph has a non-aligned straight-line drawing in an $n\times (\frac{4}{3}n-1)$-grid.

2 Non-aligned Straight-Line Drawings

In this section, all drawings are required to be straight-line drawings.

2.1 Non-aligned Drawings on an $n^2 \times n^2$-Grid

We first show how to construct non-aligned drawings in an $n^2\times n^2$-grid by scaling and perturbing a so-called weak barycentric representation (reviewed below). In the following, a vertex v is assigned to a triplet of non-negative integer coordinates $(p_0(v),p_1(v),p_2(v))$. For two vertices u, v and $i=0,1,2$, we say that $p_i(u) <_{\text {lex}} p_i(v)$ if either $p_i(u) < p_i(v)$ or $p_i(u) = p_i(v)$ and $p_{i+1}(u) < p_{i+1}(v)$. Note that in this section, addition on the subscripts is done modulo 3.

Definition 1

([16]). A weak barycentric representation of a graph G is an injective function mapping each $v\in V(G)$ to a point $(p_0(v),p_1(v),p_2(v)) \in \mathbb {N}_0^3$ such that:

• $p_0(v) + p_1(v) + p_2(v) = c$ for every vertex v, where c is a constant independent of the vertex,

• for each edge (u, v) and each vertex $w \ne \{u,v\}$, there is some $k \in \{0,1,2\}$ such that $p_k(u)<_{\text {lex}} p_k(z)$ and $p_k(v)<_{\text {lex}} p_k(z)$.

Theorem 1

([16]). Every planar graph with n vertices has a weak barycentric representation with $c=n-1$. Furthermore, $0\le p_i(v) \le n-2$ for all vertices $v\in V$ and all $i\in \{0,1,2\}$.

Observe that weak barycentric representations are preserved under scaling, i.e., if we have a weak barycentric representation $\mathcal {P}$ (say with constant c), then we can scale all assigned coordinates by the same factor N and obtain another weak barycentric representation (with constant $c\cdot N$). We need to do slightly more, namely scale and “twist”, as detailed in the following lemma (not proved here).

Lemma 1

Let G be a graph with a weak barycentric representations $\mathcal {P}=\left( \left( p_0(v),p_1(v),p_2(v)\right) _{v\in V}\right)$. Let $N\ge 1+ \max _{v\in V} \{\max _{i=0,1,2} p_i(v)\}$ be a positive integer. Define $\mathcal {P}'$ to be the assignment $p'_i(v) := N\cdot p_i(v)+p_{i+1}(v)$ for $i=0,1,2$. Then $\mathcal {P}'$ is also a weak barycentric representation.

Applying this to Schnyder’s weak barycentric representation, we now have:

Theorem 2

Every planar graph has a non-aligned straight-line planar drawing in an $(n(n-2))\times (n(n-2))$-grid.

Proof

Let $\mathcal {P}=\left( \left( p_0(v),p_1(v),p_2(v)\right) _{v\in V}\right)$ be the weak barycentric representation of Theorem 1; we know that $0\le p_i(v)\le n-2$ for all v and all i. Now apply Lemma 1 with $N=n-1$ to obtain the weak barycentric representation $\mathcal {P}'$ with $p'_i(v)=(n-1)p_i(v)+p_{i+1}(v)$. Observe that $p'_i(v)\le (n-1)(n-2)+(n-2)=n(n-2)$. Also, $p'_i(v)\ge 1$ since not both $p_i(v)$ and $p_{i+1}(v)$ can be 0. (More precisely, $p_i(v)=0=p_{i+1}(v)$ would imply $p_{i+2}(v)=n-1$, contradicting $p_{i+2}(v)\le n-2$.)

As shown by Schnyder [16], mapping each vertex v to point $(p_0'(v),p_1'(v))$ gives a planar straight-line drawing of G. By the above, this drawing has the desired grid-size. It remains to show that it is non-aligned, i.e., for any two vertices u, v and any $i \in \{0, 1\}$, we have $p'_i(u) \ne p'_i(v)$. Assume after possible renaming that $p_i(u)\le p_i(v)$. We have two cases:

• If $p_i(u) < p_i(v)$, then $p_i(u) \le p_i(v) -1$ since $\mathcal {P}$ assigns integers. Thus $N \cdot p_i(u) \le N \cdot p_i(v) - N < N\cdot p_i(v) - p_{i+1}(u) + p_{i+1}(v)$ since $p_{i+1}(u)<N$ and $p_{i+1}(v)\ge 0$. Therefore $p'_i(u) < p'_i(v)$.

• If $p_i(u) = p_i(v)$, then $p_{i+1}(u) \ne p_{i+1}(v)$ (else the three coordinates of u and v would be the same, which is impossible since $\mathcal {P}$ is an injective function). Then $p'_i(u) = N \cdot p_i(u) + p_{i+1}(u) \ne N \cdot p_i(v) + p_{i+1}(v)= p'_i(v)$.    $\square$

2.2 Non-aligned Drawings on an $n \times f(n)$-Grid

We now show how to build non-aligned drawings for which the width is the minimum-possible n, and the height is $\approx \frac{1}{2}n^3$. We use the well-known canonical ordering for triangulated plane graphs, i.e., graphs for which the planar embedding is fixed and all faces (including the outer-face) are triangles. We hence assume throughout that G is triangulated; we can achieve this by adding edges and delete them in the obtained drawing.

The canonical ordering [11] of such a graph is a vertex order $v_1,\dots ,v_n$ such that $\{v_1,v_2,v_n\}$ is the outer-face, and for any $3\le k\le n$, the graph $G_k$ induced by $v_1,\dots ,v_k$ is 2-connected. This implies that $v_k$ has at least 2 predecessors (i.e., neighbours in $G_{k-1}$), and its predecessors form an interval on the outer-face of $G_{k-1}$. We assume (after possible renaming) that $v_1$ is the neighbor of $v_2$ found in clockwise order on the outer-face, and enumerate the outer-face of graph $G_{k-1}$ in clockwise order as $c_1,\dots ,c_L$ with $c_1=v_1$ and $c_L=v_2$. Then the predecessors of $v_k$ consist of $c_\ell ,\dots ,c_r$ for some $1\le \ell < r \le L$; we call $c_\ell$ and $c_r$ the leftmost and rightmost predecessor of $v_k$ (see also Fig. 1). In this section, x(v) and y(v) denote the x- and y-coordinates of a vertex v, respectively.

Distinct x- Coordinates. We first give a construction that achieves distinct x-coordinates in $\{1,\dots ,n\}$ (but y-coordinates may coincide). Let $v_1,\dots ,v_n$ be a canonical ordering. The goal is to build a straight-line drawing of the graph $G_k$ induced by $v_1,\dots ,v_k$ using induction on k. The key idea is to define all x-coordinates beforehand. Define an orientation of the edges of G as follows. Direct $(v_1,v_2)$ as $v_1\rightarrow v_2$. For $k\ge 3$, if $c_r$ is the rightmost predecessor of $v_k$, then direct all edges from predecessors of $v_k$ towards $v_k$, with the exception of $(v_{k},c_r)$, which is directed $v_{k}\rightarrow c_r$.

By induction on k, one easily shows that the orientation of $G_k$ is acyclic, with unique source $v_1$ and unique sink $v_2$, and the outer-face directed $c_1\rightarrow \dots \rightarrow c_L$. Find a topological order $x: V\rightarrow \{1,\dots ,n\}$ of the vertices, i.e., if $u\rightarrow v$ then $x(u)<x(v)$. We use this topological order as our x-coordinates, and hence have $x(v_1)=1$ and $x(v_2)=n$. (We thus use two distinct vertex-orderings: one defined by the canonical ordering, which is used to compute y-coordinates, and one defined by the topological ordering derived from the canonical ordering, which directly gives the x-coordinates.)

Now construct a drawing of $G_k$ that respects these x-coordinates by induction on k; see also Fig. 1. Start with $v_1$ at (1, 2), $v_3$ at $(x(v_3),2)$ and $v_2$ at (n, 1).

For $k\ge 3$, let $c_\ell$ and $c_r$ be the leftmost and rightmost predecessor of $v_{k+1}$. Notice that $x(c_\ell )<\dots <x(c_r)$ due to our orientation. Let $y^*$ be the smallest integer value such that any $c_j$, for $\ell \le j\le r$, can “see” the point $p=(x(v_{k+1}),y^*)$ in the sense that that the line segment from $c_j$ to p intersects no other vertices or edges. Since $c_j$ is on the outer-face, then $c_j$ can see all points on the ray upward from $c_j$. Furthermore, by tilting this ray slightly, $c_j$ can also see all sufficiently high points on the vertical line $\{x=x(v_{k+1})\}$. Thus, such a $y^*$ exists. Placing $v_{k+1}$ at $(x(v_{k+1}),y^*)$ hence gives a planar drawing of $G_{k+1}$, and we continue until we get a drawing of $G_n=G$.

Fig. 1.

(Left) Illustration of a canonical order. (Right) Finding a y-coordinate for $v_{k+1}$.

To analyze the height of this construction, we bound the slopes.

Lemma 2

Define $s(k):=k-3$ for $k\ge 3$. All edges on the outer-face of the constructed drawing of $G_k$ have slope at most s(k) for $k \ge 3$.

Proof

(Sketch) In the drawing of $G_k$, let $\rho _\ell$ be the ray of slope s(k) starting at $c_\ell$. Consider the place where this ray intersects the vertical line $\{x=x(v_{k+1})\}$, and let $y'$ be the smallest y-coordinate of a grid point vertically above this intersection point. Hence

$$\begin{aligned} y' \le y(c_\ell ) + \left( x(v_{k+1})-x(c_\ell )\right) \cdot s(k) + 1. \end{aligned}$$

(1)

Since all edges on the outer-face of $G_k$ have slope at most s(k), one can easily verify that point $(x(v_{k+1}),y')$ can see all of $c_\ell ,\dots ,c_r$, so we have $y^*\le y'$. Also, the worst new slope among the edges of the outer-face of $G_k$ occurs at edge $(c_\ell ,v_{k+1})$, which by Eq. (1) has slope at most

$$\begin{aligned} \frac{y'-y(c_\ell )}{x(v_{k+1})-x(c_\ell )} \le s(k)+\frac{1}{x(v_{k+1})-x(c_\ell )} \le s(k)+1 = s({k+1}). \quad \quad \quad \,\, \square \end{aligned}$$

Vertex $v_n$ has x-coordinate at most $n-1$, and the edge from $v_1$ to $v_n$ has slope at most $s(n)=n-3$. This shows that the y-coordinate of $v_n$ is at most $2+(n-2) \cdot (n-3)$. Since triangle $\{v_1,v_2,v_n\}$ bounds the drawing, this gives:

Theorem 3

Every planar graph has a planar straight-line drawing in an $n\times (2+(n-2)(n-3))$-grid such that all vertices have distinct x-coordinates.

While this theorem per se is not useful for non-aligned drawings, we find it interesting from a didactic point of view: It proves that polynomial coordinates can be achieved for straight-line drawings of planar graphs, and requires for this only the canonical ordering, but neither the properties of Schnyder trees [16] nor the details of how to “shift” that is needed for other methods using the canonical ordering (e.g. [8, 11]). We believe that our bound on the height is much too big, and that the true height is $o(n^2)$ and possibly O(n).

Non-aligned Drawings. We now modify the above construction slightly to achieve distinct y-coordinates. Define the exact same x-coordinates and place $v_1$ and $v_2$ as before. To place vertex $v_{k+1}$, let $y^*$ be the smallest y-coordinate such that point $(x(v_{k+1}),y^*)$ can see all predecessors of $v_{k+1}$, and such that none of $v_1,\dots ,v_k$ is in row $\{y=y^*\}$. Clearly this gives a non-aligned drawing. It remains to bound how much this increases the height.

Observe that we use y-coordinate 3 for $v_3$, and all slopes in the drawing of $G_3$ are at most 1. All later vertices want to be placed with y-coordinate 3 or higher, and therefore have no row-conflict with $v_1$ and $v_2$. Thus when placing $v_{k+1}$, at most $k-2$ previous vertices could occupy rows that we wish to use for $y^*$. In consequence, Eq. (1) is now replaced by

$$\begin{aligned} y^* \le y(c_\ell ) + \left( x(v_{k+1})-x(c_\ell )\right) \cdot s'(k) + (k-1) \end{aligned}$$

(2)

where $s'(k)$ is the bound on the slope of the drawing of $G_k$. A proof similar to the one of Lemma 2 now shows:

Lemma 3

Define $s'(k):=\sum _{i=1}^{k-2} i = \frac{1}{2}(k-1)(k-2)$ for $k\ge 3$. All edges on the outer-face of the constructed non-aligned drawing of $G_k$ have slope at most $s'(k)$ for $k \ge 3$.

The maximal slope is hence at most $\frac{1}{2}(n-1)(n-2)$, and if applicable, achieved at edge $(v_1,v_n)$. Since $x(v_n)-x(v_1)\le n-2$ and $y(v_1)=2$, therefore the height is at most $2+\frac{1}{2}(n-1)(n-2)^2$.

Theorem 4

Every planar graph has a non-aligned straight-line drawing in an $n\times \left( 2+\frac{1}{2}(n-1)(n-2)^2\right)$-grid.

Comparing this to Theorem 2, we see that the aspect ratio is much worse, but the area is smaller. We suspect that the method results in a smaller height than the proven upper bound: Eq. (2) is generally not tight, and so a smaller slope-bound (implying a smaller height) is likely to hold.

2.3 The Special Case of Nested Triangles

We now turn to non-aligned drawings of a special graph class. Define a nested-triangle graph G as follows. G has 3k vertices for some $k\ge 1$, say $\{u_i,v_i,w_i\}$ for $i=1,\dots ,k$. Vertices $\{u_i,v_i,w_i\}$ form a triangle (for $i=1,\dots ,k$). We also have paths $u_1,u_2,\dots ,u_k$ as well as $v_1,v_2,\dots ,v_k$ and $w_1,w_2,\dots ,w_k$. With this the graph is 3-connected; we assume that its outer-face is $\{u_1,v_1,w_1\}$. All interior faces that are not triangles may or may not have a diagonal in them, and there are no restrictions on which diagonal (if any). Nested-triangle graphs are of interest in graph drawing because they are the natural lower-bound graphs for the area of straight-line drawings [10].

Theorem 5

Any nested-triangle graph with $n=3k$ vertices has a non-aligned straight-line drawing in an $n\times (\frac{4}{3}n-1)$-grid.

Proof

The 4-cycle $\{w_k,v_k,v_{k-1},w_{k-1}\}$ may or may not have a diagonal in it; after possible exchange of $w_1,\dots ,w_k$ and $v_1,\dots ,v_k$ we assume that there is no edge between $v_{k-1}$ and $w_k$. For $i=1,\dots ,k$, place $u_i$ at (i, i), vertex $v_i$ at $(3k+1-i, k+i)$, and $w_i$ at $(k+i,4k+1-2i)$ (see Fig. 2). The x- and y-coordinates are all distinct. The x-coordinates range from 1 to n, and the maximal y-coordinate is $4k-1 = \frac{4}{3}n-1$. It is easy to check that all interior faces are drawn strictly convex, with the exception of $\{v_k,v_{k-1},w_{k-1},w_k\}$ which has a $180^\circ$ angle at $v_k$, but our choice of naming ensured that there is no edge $(v_{k-1},w_k)$. Thus any diagonal inside these 4-cycles can be drawn without overlap. Since G is planar, two edges joining vertices of different triangles cannot cross. Thus G is drawn without crossing in an $n \times \left( \frac{4}{3}n-1 \right)$-grid.    $\square$

In particular, notice that the octahedron is a nested-triangle graph (for $k=2$) and this construction gives a non-aligned straight-line drawing in a $6\times 7$-grid. This is clearly optimal since it has no straight-line rook-drawing [2].

We conjecture that this construction gives the minimum-possible height for nested-triangle graphs among all non-aligned straight-line drawings.

Fig. 2.

A non-aligned straight-line drawing of a nested-triangle graph with $k=3$ on an $9 \times 11$-grid, an RI-drawing satisfying the conditions of Theorem 6, and combining two RI-drawings if all separating triangles contain (u, w).

3 Rook-Drawings with Bends

We now construct rook-drawings with bends; as before we do this only for triangulated graphs. The main idea is to find rook-drawings with only 1 bend for 4-connected triangulated graphs. Then convert any graph into a 4-connected triangulated graph by subdividing few edges and re-triangulating, and argue that the drawing for it, modified suitably, gives a rook-drawing with few bends.

We need a few definitions first. Fix a triangulated graph G. A separating triangle is a triangle that has vertices both strictly inside and strictly outside the triangle. G is 4-connected (i.e., cannot be made disconnected by removing 3 vertices) if and only if it has no separating triangle. A filled triangle [5] of G is a triangle that has vertices strictly inside. Graph G has at least one filled triangle (namely, the outer-face) and every separating triangle is also a filled triangle. We denote by $f_G$ the number of filled triangles of the graph G. A rectangle-of-influence (RI) drawing is a straight-line drawing such that for any edge (u, v), the minimum axis-aligned rectangle containing u and v is empty in the sense that it contains no other vertex of the drawing in its relative interior (see Fig. 2). The following is known:

Theorem 6

([5]). Let G be a triangulated 4-connected graph and let e be an edge on the outer-face. Then $G-e$ has a planar RI-drawing. Moreover, the drawing is non-aligned and on an $n\times n$-grid, the ends of e are at (1, n) and (n, 1), and the other two vertices on the outer-face are at (2, 2) and $(n-1,n-1)$.

The latter part of this claim is not specifically stated in [5], but can easily be inferred from the construction (see also a simpler exposition in [4]). RI-drawings are useful because they can be deformed (within limits) without introducing crossings. We say that two drawings $\varGamma$ and $\varGamma '$ of a graph have the same relative coordinates if for any two vertices v and w, we have $x_\varGamma (v)<x_\varGamma (w)$ if and only if $x_{\varGamma '}(v)<x_{\varGamma '}(w)$, and $y_\varGamma (v)<y_\varGamma (w)$ if and only if $y_{\varGamma '}(v)<y_{\varGamma '}(w)$, where $x_\varGamma (v)$ denotes the x-coordinate of v in $\varGamma$, etc. The following result appears to be folklore; we sketch a proof for completeness.

Observation 1

Let $\varGamma$ be an RI-drawing. If $\varGamma '$ is a straight-line drawing with the same relative coordinates as $\varGamma$, then $\varGamma '$ is an RI-drawing, and it is planar if and only if $\varGamma$ is.

Proof

The claim on the RI-drawing was shown by Liotta et al. [14]. It remains to argue planarity. Assume that edge (u, v) crosses edge (w, z) in an RI-drawing. Since all rectangles-of-influence are empty, this happens if and only if (up to renaming) we have $x(w)\le x(u)\le x(v)\le x(z)$ and $y(u)\le y(w)\le y(z)\le y(v)$. This only depends on the relative orders of u, v, w, z, and hence a transformation that maintains relative coordinates maintains planarity.   $\square$

We need a slight strengthening of Theorem 6.

Lemma 4

Let G be a triangulated graph, let $e\in E$ be an edge on the outer-face, and assume all separating triangles contain e. Then $G-e$ has a planar RI-drawing. Moreover, the drawing is non-aligned and on an $n\times n$-grid, the ends of e are at (1, n) and (n, 1), and the other two vertices on the outer-face are at (2, 2) and $(n-1,n-1)$.

Proof

We proceed by induction on the number of separating triangles of G. In the base case, G is 4-connected and the claim holds by Theorem 6. For the inductive step, assume that $T=\{u,x,w\}$ is a separating triangle. By assumption it contains e, say $e=(u,w)$. Let $G_1$ be the graph consisting of T and all vertices inside T, and let $G_2$ be the graph obtained from G by removing all vertices inside T. Apply induction to both graphs. In drawing $\varGamma _2$ of $G_2-e$, vertex x is on the outer-face and hence placed at (2, 2). Now insert a (scaled-down) copy of the drawing $\varGamma _1$ of $G_1$, minus vertices u and w, in the square $(1,2]\times (1,2]$ (see Fig. 2). Since x was in the top-right corner of $\varGamma _1-\{u,w\}$, the two copies of x can be identified. One easily verifies that this gives an RI-drawing, because within each drawing the relative coordinates are unchanged, and the two drawings are disjoint except at u and w. Finally, re-assign coordinates to the vertices while keeping relative coordinates intact so that we have an $n\times n$-grid; by Observation 1 this gives a planar RI-drawing.    $\square$

3.1 4-Connected Planar Graphs

Combining Theorem 6 with Observation 1, we immediately obtain:

Theorem 7

Let G be a triangulated 4-connected planar graph. Then G has a planar rook-drawing with at most one bend.

Proof

Fix an arbitrary edge e on the outer-face, and apply Theorem 6 to obtain an RI-rook-drawing $\varGamma$ of $G-e$ (see Fig. 3(a)). It remains to add in edge $e=(u,v)$. One end u of e is in the top-left corner, and the leftmost column contains no other vertex. The other end v is in the bottom-right corner, and the bottommost row contains no other vertex. We can hence route (u, v) by going vertically from u and horizontally from v, with the bend in the bottom-left corner.   $\square$

Corollary 1

Let G be a 4-connected planar graph. Then G has a rook-drawing with at most one bend, and with no bend if G is not triangulated.

Proof

If G is triangulated then the result was shown above, so assume G has at least one face of degree 4 or more. Since G is 4-connected, one can add edges to G such that the result $G'$ is triangulated and 4-connected [6]. Pick a face incident to an added edge e as outer-face of $G'$, and apply Theorem 6 to obtain an RI-drawing of $G'-e$. Deleting all edges in $G'-G$ gives the result.   $\square$

Since we have only one bend, and the ends of the edge (u, v) that contain it are the top-left and bottom-right corner, we can remove the bend by stretching.

Theorem 8

Every 4-connected planar graph has a non-aligned planar drawing in an $n\times (n^2-3n+4)$-grid and in a $(2n-2) \times (2n-2)$-grid.

Proof

Let $\varGamma$ be the RI-drawing of $G-(u,v)$ with u at (1, n) and v at (n, 1). Relocate u to point $(1,n^2-3n+4)$. The resulting drawing is still a planar RI-drawing by Observation 1. Now $y(u)-y(v)=(n-2)(n-1)+1$, hence the line segment from u to v has slope less than $-(n-2)$, and is therefore above point $(n-1,n-1)$ (and hence above all other vertices of the drawing). So we can add this edge without violating planarity, and obtain a non-aligned straight-line drawing of G (see Fig. 3(b)). For the other result, start with the same drawing $\varGamma$. Relocate u to $(1,2n-2)$ and v to $(2n-2,1)$. The line segment from u to v has slope $-1$ and crosses $\varGamma$ only in the top right grid-square, which was empty. So we obtain a non-aligned planar straight-line drawing. (see Fig. 3(c)).   $\square$

Fig. 3.

An RI-rook-drawing of $G-e$, transformation into a non-aligned drawing of G of width n (where the top-left corner moved sufficiently high), and a second non-aligned drawing of G.

3.2 Constructing Rook-Drawings with Few Bends

We now explain the construction of a (poly-line) rook-drawing for a triangulated graph G with at least 5 vertices. We proceed as follows:

• 1. Find a small independent-filled-hitting set $E_f$. Here, an independent-filled-hitting set $E'$ is a set of edges such that (i) every filled triangle has at least one edge in $E'$ (we say that $E'$ hits all filled triangles), and (ii) every face of G has at most one edge in $E'$ (we say that $E'$ is independent). We can show the following bound:

Lemma 5

Any triangulated graph G of order n has an independent-filled-hitting set of size at most

• $f_G$ (where $f_G$ is the number of filled triangles of G), and it can be found in O(n) time,

• $\frac{2n-5}{3}$, and it can be found in $O((n\log n)^{1.5}\alpha (n,n))$ time (where $\alpha$ denotes the inverse Ackermann function) or approximated arbitrarily close in O(n) time.

Proof

(Sketch) Compute a 4-coloring of the planar graph G, defining three perfect matchings in the dual graph. Let $M_1,M_2,M_3$ be the corresponding edge sets in G, and let $E_i$ (for $i=1,2,3$) be $M_i$ with all edges removed that do not belong to a filled triangle. Since $M_i$ stems from a 4-coloring, it contains exactly one edge of each triangle, hence $E_i$ hits all filled triangles and $|E_i|\le f_G$. Since $M_i$ is the dual of a matching, $E_i$ is independent. Cardinal et al. [7] showed that any planar graph has at most $2n-7$ edges that belong to a separating triangle, and similarly one can show that at most $2n-5$ edges belong to a filled triangle (there are $2n-5$ interior faces, and we can assign to each edge in a filled triangle the face on its “interior” side without double-counting faces). Therefore the best of $E_1,E_2,E_3$ contains at most $(2n-5)/3$ edges. To find it, we can either compute a minimum-weight perfect matching for suitable weights [12], or approximate it with a linear-time PTAS based on Baker’s technique [3].    $\square$

Fig. 4.

(a, b) A separating triangle removed by subdividing and re-triangulating. (c) The RI-drawing of Fig. 2 reordered such that subdivision vertices (grey) are not at integer coordinates. (d) The drawing of (c), with subdivison vertices shifted to integer gridpoints.

• 2. Since the outer-face is a filled triangle, there exists one edge $e_o\in E_f$ that belongs to the outer-face. Define $E_s:=E_f-\{e_o\}$ and notice that $E_s$ contains no outer-face edges since $E_f$ is independent.

• 3. As done in some previous papers [7, 13], remove separating triangles by subdividing all edges $e\in E_s$, and re-triangulate by adding edges from the subdivision vertex (see Fig. 4(a, b)). Let $V_x$ be the new set of vertices, and let $G_1$ be the new graph. Observe that $G_1$ may still have separating triangles, but all those separating triangles contain $e_o$ since $E_f$ hits all filled triangles.

• 4. By Lemma 4, $G_1-e_o$ has a non-aligned RI-drawing $\varGamma$ where the ends of $e_o$ are at the top-left and bottom-right corner.

• 5. Transform $\varGamma$ into drawing $\varGamma '$ so that the relative orders stay intact, the original vertices (i.e., vertices of G) are on an $n\times n$-grid and the subdivision vertices (i.e., vertices in $V_x$) are inbetween.

  This can be done by enumerating the vertices in x-order, and assigning new x-coordinates in this order, increasing to the next integer for each original vertex and increasing by $\frac{1}{|V_x|+1}$ for each subdivision vertex. Similarly update the y-coordinates (see Fig. 4(c)). Drawing $\varGamma '$ is still a non-aligned RI-drawing, and the ends of $e_o$ are on the top-left and bottom-right corner.

• 6. Let e be an edge in $E_s$ with subdivision vertex $x_e$. Since e is an interior edge of G, $x_e$ is an interior vertex of $G_1$. Now move $x_e$ to some integer gridpoint nearby. This is possible due to the following (not proved here):

Lemma 6

Let $\varGamma$ be a planar RI-drawing. Let x be an interior vertex of degree 4 with neighbours $u_1,u_2,u_3,u_4$ that form a 4-cycle. Assume that none of $x,u_1,u_2,u_3,u_4$ share a grid-line. Then we can move x to a point on grid-lines of its neighbours and obtain a planar RI-drawing.

• Note that the 4-cycle among the neighbours of $x_e$ contains no other vertices in $V_x$, since $E_s$ was independent. So any two subdivision vertices are separated via such a 4-cycle, and we can apply this operation to any subdivision-vertex independently.

• 7. Now replace each subdivision-vertex $x_e$ by a bend, connected to the ends of e along the corresponding edges from $x_e$, see Fig. 4(d). (Sometimes, as is the case in the example, we could also simply delete the bend and draw edge e straight-line.) None of the shifting changed positions for vertices of G, so we now have a rook-drawing of $G-e_o$ with bends. The above shifting of vertices does not affect outer-face vertices, so the ends of $e_o$ are still in the top-left and bottom-right corner. As the final step draw $e_o$ by drawing vertically from one end and horizontally from the other; these segments are not occupied by the rook-drawing.

We added one bend for each edge in $E_f$. By Lemma 5, we can find an $E_f$ with $|E_f|\le f_G$ and $|E_f|\le \frac{2n-5}{3}$ (neither bound is necessarily smaller than the other), and hence have:

Theorem 9

Any planar graph G of order n has a planar rook-drawing with at most b bends, with $b\le \min \{ \frac{2n-5}{3}, f_G\}$.

4 Conclusion

In this paper, we continued the work on planar rook-drawings initiated by Auber et al. [2]. We constructed planar rook-drawings with at most $\frac{2n-5}{3}$ bends; the number of bends can also be bounded by the number of filled triangles. We also considered drawings that allow more rows and columns while keeping vertices on distinct rows and columns; we proved that such non-aligned planar straight-line drawings always exist and have area $O(n^4)$. As for open problems, the most interesting question is lower bounds. No planar graph is known that needs more than one bend in a planar rook-drawing, and no planar graph is known that needs more than $2n+1$ grid-lines in a planar non-aligned drawing. The “obvious” approach of taking multiple copies of the octahedron fails because the property of having a rook-drawing is not closed under taking subgraphs: if vertices are added, then they could “use up” extraneous grid-lines in the drawing of a subgraph. We conjecture that the $n\times (\frac{4}{3}n-1)$-grid achieved for nested-triangle graphs is optimal for planar straight-line non-aligned drawings with width n.