1. Introduction
Recently automatic aesthetic drawing of graphs has created intense interest due to their broad applications, and as a consequence, a number of drawing methods have come out [1]-[13], [16]-[19], [22]-[24]. The most typical drawing of a plane graph \(G\) is a straight-line drawing, in which all vertices of \(G\) are drawn as points and all edges are drawn as straight-line segments without any edge-intersection. A straight-line drawing is called a grid drawing if all vertices are put on grid points of integer coordinates. The integer grid of size \(W \times H\) consists of \(W+1\) vertical segments and \(H+1\) horizontal segments, and has a rectangular contour. \(W\) and \(H\) are called the width and height of the integer grid, respectively. It is known that every plane graph of \(n \ge 3\) vertices has a grid drawing on an \((n-2)\times(n-2)\) grid, and that such a grid drawing can be found in linear time [3], [5], [6], [23]. Figure 1 depicts three grid drawings of the same plane graph. On the other hand, a restricted class of graphs has a more compact grid drawing. For example, if \(G\) is a 4-connected plane graph and has at least four vertices on its outer face, then \(G\) has a grid drawing on a \(W\times H\) grid such that \(W=\lceil n/2 \rceil-1\) and \(H=\lfloor n/2 \rfloor\), and one can find such a grid drawing in linear time [19]. Furthermore, if \(G\) is a 5-connected plane graph and has at least five vertices on its outer face, then \(G\) has a grid drawing on a \(W\times H\) grid such that \(W + H \leq n-2\), and one can find such a grid drawing in linear time [16]. There are some special classes of plane graphs which require small areas for straight line drawing [7]. For example, a subclass of five connected plane graph requires \(O(n)\) area [13]. Some outerplanar graphs require areas smaller than quadratic area [8], [12].
 |
Fig. 1 (a) A closed RI-drawing, (b) an open RI-drawing, and (c) a non-RI-drawing of an inner triangulated plane graph. |
There are many results on straight-line drawings under additional constraints. A proximity drawing of a graph is a straight-line drawing where the points representing adjacent vertices are deemed to be close according to some proximity measure. Proximity drawings have been intensively studied in recent years because they arise in many areas including pattern recognition, geographic information systems, and computer vision [10].
In the paper, we deal with a type of a proximity drawing of a plane graph, known as a “rectangle-of-influence drawing” [1], [15], [17], [18]. A rectangle-of-influence of an edge \(e\) is an axis-parallel rectangle having \(e\) as one of its diagonals. In each of Figs. 1(a)-(c) a rectangle-of-influence is shaded for an edge \(e=(u,v)\) drawn by a thick line. We call a grid drawing a rectangle-of-influence drawing (or simply an RI-drawing) if there is no vertex in a rectangle-of-influence of any edge. Figures 1(a) and (b) depict RI-drawings, while Fig. 1(c) depicts a grid drawing which is not an RI-drawing. An RI-drawing often looks pretty, since vertices tend to be separated from edges. A rectangle-of-influence of an edge \(e\) is closed if it contains the boundary of a rectangle, and is open if it does not contain the boundary. In a closed RI-drawing every rectangle-of-influence is regarded as a closed one, while in an open RI-drawing every rectangle-of-influence is regarded as an open one. In a closed RI-drawing, there is no vertex except the ends not only in the proper inside of a rectangle-of-influence of each edge but also on the boundary, as illustrated in Fig. 1(a). In an open RI-drawing, there may be a vertex other than the ends on the boundary of a rectangle, as illustrated in Fig. 1(b). Thus a closed RI-drawing is an open RI-drawing, but an open RI-drawing is not always a closed RI-drawing.
Biedl et al. showed that a plane graph \(G\) has a closed RI-drawing on an \((n-1) \times (n-1)\) grid if there is no vertices in the interior of an any 3-cycle [1]. Furthermore, Miura et al. gave a sufficient condition for an inner triangulated plane graph \(G\) to have an open RI-drawing, and they also gave an \(O({n^{1.5}}/{\log n})\)-time algorithm to construct an open RI-drawing of \(G\) on an \((n-1) \times (n-1)\) grid, whenever \(G\) has one [17]. It is also known that every 4-connected plane graph with four or more vertices on the outer facial cycle has an open RI-drawing on a smaller grid, that is, a \(W \times H\) grid with \(W+H \le n-1\), and such a drawing can be found in linear time [18], where \(W\) and \(H\) are the width and height of an integer grid, respectively. Since \(W+H \le n-1\), the area \(W \times H\) satisfies \(W \times H \le \lceil (n-1)/2 \rceil \cdot \lfloor (n-1)/2 \rfloor\). The size of an integer grid required by an open RI-drawing would be smaller than \((\lceil (n-1)/2 \rceil) \times (\lfloor (n-1)/2 \rfloor)\) for 5-connected plane graphs, but it has not been known how small the grid size is.
In this paper, we show that the grid drawing of a 5-connected plane graph \(G\) found by the algorithm in [16] is always an open RI-drawing of \(G\), and hence one can find in linear time an open RI-drawing of \(G\) on a \(W \times H\) grid such that \(W+H \le n-2\) if \(G\) has five or more vertices on the outer face. Since \(W + H \leq n-2\), \(W \cdot H \leq \lceil (n-2)/2\rceil \cdot \lfloor (n-2)/2\rfloor\) and hence our bounds on \(W + H\) and \(W \cdot H\) are (slightly) better than Miura, et al.’s bounds [18]. Actually, it is known that there exists an infinite number of five-connected plane graphs of \(n\) vertices, for example the nested pentagons-like graph as illustrated in Fig. 2, which needs a grid of size at least \(\{\lfloor 2(n-6)/5\rfloor+2\} \times \{\lfloor 2(n-6)/5\rfloor +2\}\) for any open RI-drawing. It will be conjectured that every 5-connected plane graph \(G\) has an open RI-drawing on a \(\lfloor 2n/5\rfloor \times \lfloor 2n/5\rfloor\) grid, that is \(W + H \leq 4n/5\), and hence there is still a gap between our bounds and the lower bounds.
 |
Fig. 2 A five connected plane graph attaining the lower bounds. |
The remainder of this paper is organized as follows. In Sect. 2 we give some definitions and a known lemma. In Sect. 3 we present the linear-time algorithm in [16] for finding a grid drawing of a 5-connected plane graph. In Sect. 4 we prove that the grid drawing is an open RI-drawing. Finally we conclude in Sect. 5.
2. Preliminaries
In this section, we give some definitions and a known lemma.
Let \(G=(V,E)\) be a simple connected graph having no multiple edge or loop. \(V\) is the vertex set and \(E\) is the edge set of \(G\). Let \(n\) be the number of vertices of \(G\). An edge joining vertices \(u\) and \(v\) is denoted by \((u,v)\). The connectivity \(\kappa(G)\) of a graph \(G\) is the minimum number of vertices whose removal results in a disconnected graph or a single-vertex graph \(K_1\). A graph \(G\) is k-connected if \(\kappa(G)\ge k\).
A graph is planar if it can be embedded in the plane so that no two edges intersect geometrically except at a vertex to which they are both incident. A plane graph is a planar graph with a fixed embedding in the plane. A plane graph divides the plane into connected regions called faces. We denote the boundary of a face by a clockwise sequence formed by the vertices and edges on the boundary. We call the boundary of the outer face of a plane graph \(G\) the contour of \(G\), and denote it by \(C_o(G)\). A plane graph \(G\) is internally triangulated if all inner faces of \(G\) are triangles. We can assume without loss of generality that a given graph \(G\) is internally triangulated. Otherwise, we internally triangulate \(G\) by adding some new edges to \(G\), find a drawing of the resulting graph, and finally remove the added edges to obtain a drawing of \(G\). Let \(x(v)\) and \(y(v)\) be the x- and y-coordinates of vertex \(v \in V\), respectively. We denote the current position of a vertex \(v\) by \(P(v)\); \(P(v)\) is expressed by its x- and y-coordinates as \((x(v),y(v))\). We say that a curve in the plane is x-monotone if the intersection of the curve and any vertical line is a single point when it is nonempty.
We then introduce the definition of a 5-canonical decomposition of a plane graph \(G\) [20], [21], which plays a crucial role in the algorithm in [16]. It is a generalization of two well-known concepts: the “canonical ordering,” which is used to find a grid drawing of triangulated plane graph [4]-[6], [11]; and the “4-canonical ordering,” which is used to find a grid drawing of 4-connected plane graph [9], [14], [19]. Let \(G = (V, E)\) be a 5-connected internally triangulated plane graph with five designated distinct vertices \(a_1,a_2,a_3,a_4\) and \(a_5\) on \(C_o(G)\). We may assume that the five vertices \(a_1,a_2,a_3,a_4\) and \(a_5\) appear on \(C_o(G)\) in this order. Let \(C_o(G)=(z_1=a_1,z_2, \cdots ,z_a=a_2,z_{a+1}, \cdots ,z_b=a_3, z_{b+1}, \cdots ,z_c=a_4, z_{c+1}, \cdots ,z_d=a_5,z_{d+1}, \cdots)\). We add to \(G\) one vertex \(r\) and three edges \((a_1,a_3)\), \((a_4,r)\) and \((a_5,r)\) so that \(a_1,a_3,a_4,r\) and \(a_5\) appear on the outer face of the resulting plane graph. Let \(G'\) be the resulting plane graph. (See Fig. 3(b).) For a set \(U_1,U_2, \cdots ,U_k\) of pairwise disjoint subsets of \(V\), we denote by \(G_k\) the subgraph of \(G'\) induced by \(U_1 \bigcup U_2 \bigcup \cdots \bigcup U_k\), and by \(\overline{G_k}\) the subgraph of \(G'\) induced by \((V \bigcup \{r\}) - (U_1 \bigcup U_2 \bigcup \cdots \bigcup U_k)\). Especially for \(k=0\) we define \(\overline{G_k}=G'\). We say that a partition \(\Pi = (U_1, U_2, \cdots, U_l)\) of \(V\) is a 5-canonical decomposition of \(G\) if the following four conditions (co1)-(co4) are satisfied.
(co1) \(U_1 = U^o_1 \bigcup U^i_1\) where \(U^o_1=\{z_2,z_3, \cdots ,z_{b-1}\}\) and \(U^i_1\) is the set of vertices having at least one neighbor in \(U^o_1\), (So \(a_1,a_2,a_3 \in U_1\). See Fig. 3(b).)
(co2) \(U_l=\{z_c,z_{c+1} \cdots ,z_d\}\),
(co3) For each \(k\), \(1 \leq k \leq l\), \(G_k\) is triconnected, and for each index \(k\), \(0 \leq k \leq l-1\), \(\overline{G_k}\) is biconnected, and
(co4) For each \(k\), \(2 \leq k \leq l-1\), one of the following two conditions holds (See Fig. 4. The vertices in \(U_k\) are drawn in black dots.):
(a) \(|U_k| = 1\), the vertex \(u \in U_k\) is both on \(C_o(G_k)\) and \(C_o(\overline{G_{k-1}})\), and satisfies \(d(u,G_k) \ge 3\) and \(d(u,\overline{G_{k-1}}) \ge 2\). (See Fig. 4(a).)
(b) \(|U_k| \ge 2\), the vertices in \(U_k\) appear consecutively both on \(C_o(G_k)\) and \(C_o(\overline{G_{k-1}})\), and each vertex \(u \in U_k\) satisfies \(d(u,G_k)=3\) and \(d(u,\overline{G_{k-1}}) \ge 3\). (See Fig. 4(b).)
 |
Fig. 3 (a) Five-connected internally triangulated plane graph \(G\) and (b) its 5-canonical decomposition. |
 |
Fig. 4 Two conditions for (co4). |
Although the definition above of a 5-canonical decomposition is slightly different from that in [20], [21] (conditions (co4)(a) and (b) have been swapped), they are effectively equivalent to each other. A 5-canonical decomposition \(\Pi = (U_1,U_2, \cdots\), \(U_{12})\) of the graph in Fig. 3(a) is illustrated in Fig. 3(b). Note that since \(G\) is internally triangulated (co4)(b) means the vertices in \(U_k\) share a common neighbor on \(C_o(G_{k-1})\).
The following lemma is known.
Lemma 1: [20], [21] Let \(G=(V,E)\) be a 5-connected internally triangulated plane graph with five designated distinct vertices \(S=\{a_1,a_2,a_3,a_4,a_5\}\) on \(C_o(G)\). Then \(G\) has a 5-canonical decomposition \(\Pi=(U_1,U_2, \cdots ,U_l)\). Furthermore \(\Pi\) can be found in linear time.
By the conditions (co1), (co2) and (co4), all the vertices in \(U_k\), \(1 \leq k \leq l\), consecutively appear clockwise on \(C_o(G_k)\). So we first assume that all the vertices in \(U_1\) consecutively appear clockwise on \(C_o(G_k)\) starting from \(a_1=z_1\). We then number all vertices of \(G\) by \(1,2, \cdots ,n\) where \(1=a_1\), so that they appear in \(U_1,U_2, \cdots ,U_l\) in this order, as illustrated in Fig. 3(b), and let \(n(v)\) be the number of \(v\). Thus one can define an order \(<\) among the vertices in \(G\).
For any vertices \(u,v \in V\), we write \(u \prec v\) iff \(1 \le n(u) < n(v) \le n\), and write \(u \preceq v\) iff \(1 \le n(u) \leq n(v) \le n\). We say that a vertex \(u\) in a graph \(G\) is a smaller neighbor of \(v\) if \(u\) is a neighbor of \(v\) and \(n(u)\) is smaller than \(n(v)\), that is \(u \prec v\). Similarly, we say that \(u\) is a larger neighbor of \(v\) if \(u\) is a neighbor of \(v\) and \(u \succ v\).
3. Drawing Algorithm in [16]
In this section, we present the algorithm in [16], and give some known lemmas. Before giving the detail of the algorithm, we need some preparation.
Let \(G\) be a 5-connected internally triangulated plane graph with five designated distinct vertices \(S=\{a_1,a_2,a_3,a_4,a_5\}\) on \(C_o(G)\) and let \(\Pi=(U_1,U_2, \cdots ,U_l)\) be a 5-canonical decomposition of \(G\). Throughout the remainder of this paper, we replace for simplicity the definitions of \(G_k\) and \(\overline{G_k}\), as follows. For a set \(U_1,U_2, \cdots ,U_k\) of 5-canonical decomposition of \(G\), we denote by \(G_k\) the subgraph of \(G\) (instead of \(G'\)) induced by \(U_1 \bigcup U_2 \bigcup \cdots \bigcup U_k\), and by \(\overline{G_k}\) the subgraph of \(G\) (instead of \(G'\)) induced by \(V - (U_1 \bigcup U_2 \bigcup \cdots \bigcup U_k)\).
The algorithm in [16] will add to a drawing the vertices in set \(U_k\), one by one, in the order \(U_1,U_2, \cdots ,U_l\), adjusting the drawing at each step, as illustrated in Fig. 5, by using so-called the “shift methods” given by Chrobak and Kant [3] and de Fraysseix et al. [6]. With each vertex \(v\), a set of vertices need to be moved whenever the position of \(v\) is adjusted. We denote by \(L(v)\) the set of such vertices. Let \(D(G_k)\), \(1 \le k \le l\), be the drawing of \(G_k\) obtained by the algorithm. For each index \(k\), \(2 \le k \le l\), y-coordinates of all vertices in \(U_k=\{u_1,u_2, \cdots ,u_r\}\) are decided as the same integer, which is denoted by \(y(U_k)\).
 |
Fig. 5 Some of the drawing processes of the algorithm. |
We are now ready to present the algorithm in [16]. It suffices to decide only the coordinates of all vertices of \(G\), because one can immediately find a straight line drawing from the coordinates. We are now explain how to decide the x- and y-coordinates of the vertices in \(U_k\) for each \(1 \le k \le l\). There are the following three cases to consider.
Case 1: \(k=1\). (See Fig. 5(a).)
We draw \(C_o(G_1)=(w_1(=a_3),w_2, \cdots ,w_{f-1}, w_f(=a_1),\) \(w_{f+1}, \cdots ,w_t)\) as follows. We set \(P(w_1)=(0,0)\), \(P(w_f)=(f-1,0)\), \(P(w_i)=(i-1,1)\) for all indices \(i=2,3, \cdots ,f-1\), \(P(w_t)=(1,0)\) and \(P(w_j)=(x(w_{j+1})+1,0)\) for all indices \(j=t-1,t-2, \cdots ,f+1\), as illustrated in Fig. 5(a) for the graph in Fig. 3(a). Also we set \(L(w_i)=\{w_i\}\) for each index \(i=1,2, \cdots ,t\).
Case 2: \(2 \le k \le l-1\). (See Figs. 6 and 7.)
There are the following two cases to consider.
Case 2(a): \(U_k\) satisfies condition (a) of (co4) as illustrated in Fig. 6.
 |
Fig. 6 Illustrations for Case 2(a). |
Let \(U_k=\{u\}\). Let \(C_o(G_{k-1})=(w_1,w_2, \cdots ,w_f, \cdots ,\) \(w_t)\) be the outer cycle of \(G_{k-1}\) where \(w_1=a_3\) and \(w_f=a_1\) and let \(w_p,w_{p+1}, \cdots ,w_q\) be the smaller neighbors of \(u\).
We first set \(L(u)=\{u\} \bigcup (\bigcup_{i=p+1}^{q-1}L(w_i))\). The algorithm puts \(u\) above one of its smaller neighbors so that the width \(W\) of the drawing of \(G\) becomes as small as possible. Let \(w_s\) be the smallest vertex among \(w_{p+1},w_{p+2}, \cdots ,w_{q-1}\). We then set \(x(u)=x(w_s)\).
We then explain how to decide \(y(U_k)=y(u)\). Let \(y_{max}\) be the maximum value of y-coordinates of \(w_p,w_{p+1}, \cdots ,w_q\), then one can easily know that either \(y_{max}=y(w_p)\) or \(y_{max}=y(w_q)\) by Lemma 4(b) as described later. Clearly we must decide \(y(U_k)\) so that \(y(U_k) \geq y_{max}\), in order to obtain a straight line drawing of \(G_k\). The algorithm decides \(y(U_k)\) to be either \(y_{max}\) or \(y_{max}+1\) so that the height \(H\) of the drawing of \(G\) becomes as small as possible. There are the following two cases to consider.
Case 2(a)(i): Either \(y_{max}=y(w_p) = y(w_{p+1})\) or \(y_{max}=y(w_{q-1}) = y(w_q)\). (See Figs. 6(a) and (c).)
In this case, if we set \(y(U_k)=y_{max}\), then \(D(G_k)\) would not be a straight line drawing. Therefore we set \(y(U_k)=y_{max}+1\), as illustrated in Figs. 6(b) and (d).
Case 2(a)(ii): Otherwise. (See Figs. 6(e) and (g).)
In this case, one of the following (1) or (2) holds and we set \(y(U_k)=y_{max}\), as illustrated in Figs. 6(f) and (h).
(1) Either \(y_{max}=y(w_q) > y(w_p)\) or \(y_{max}=y(w_p) > y(w_q)\). (See Fig. 6(e).)
(2) \(y_{max}=y(w_p) = y(w_q)\). (See Fig. 6(g).)
Case 2(b): \(U_k\) satisfies condition (b) of (co4) as illustrated in Fig. 7.
 |
Fig. 7 Illustrations for Case 2(b). |
Let \(U_k=\{u_1,u_2, \cdots ,u_r\}\) and let \(C_o(G_{k-1})=(w_1,w_2, \cdots ,w_f, \cdots ,w_t)\) be the outer cycle of \(G_{k-1}\) where \(w_1=a_3\) and \(w_f=a_1\). Let \(w_{p+1}\) be the common neighbor of all vertices \(u_1,u_2, \cdots ,u_r\) in \(U_k\) and let \(w_p\) and \(w_{p+2}\) be the preceding and the succeeding vertex of \(w_{p+1}\) on \(C_o(G_{k-1})\), respectively.
We first set \(L(u_r)=\{u_r\} \bigcup L(w_{p+1})\), and \(L(u_i)=\{u_i\}\) for all indices \(i=1,2, \cdots ,r-1\). The shift operation on a vertex \(w_j\), denoted by \(shift(w_j)\), is achieved by increasing the x-coordinate of each vertex \(u \in \bigcup_{i=j}^f L(w_i)\) by 1 [3]-[6], [9], [11], [19]. Then, we execute \(shift(w_{p+1})\) by \(r-1\) times, that is, we increase the x-coordinates of all vertices \(L(w_{p+1}), L(w_{p+2}), \cdots ,L(w_f)\) by \(r-1\), as illustrated in Figs. 7(b), (d), (f) and (h). For each \(i=1,2, \cdots ,r\), we set \(x(u_i)=x(w_p)+i\), as illustrated in Figs. 7(b), (d), (f) and (h). Since \(x(w_{p+2}) -x(w_p) \geq 2\) in \(D(G_{k-1})\) and \(x(w_{p+2})\) increases by \(r-1\) in \(D(G_k)\), we have \(x(w_{p+2}) -x(w_p) \geq r+1\) in \(D(G_k)\).
We then explain how to decide \(y(U_k)\). Let \(y_{max}\) be the maximum value of y-coordinates of \(w_p,w_{p+1},w_{p+2}\). Clearly we must decide \(y(U_k)\) so that \(y(U_k) \ge y_{max}\), in order to obtain a straight line drawing of \(G_k\). The algorithm decides \(y(U_k)\) to be either \(y_{max}\) or \(y_{max}+1\) similarly as Case 2(a) above. There are the following two cases:
Case 2(b)(i): \(y_{max}=y(w_{p+1})\). (See Figs. 7(a) and (c).)
In this case, if we set \(y(U_k)=y_{max}\), then \(D(G_k)\) would not be a straight line drawing. Therefore we set \(y(U_k)=y_{max}+1\), as illustrated in Figs. 7(b) and (d).
Case 2(b)(ii): Otherwise. (See Figs. 7(e) and (g).)
In this case, one of the following (1) or (2) holds and we set \(y(U_k)=y_{max}\), as illustrated in Figs. 7(f) and (h).
(1) Either \(y_{max}=y(w_{p+2}) > y(w_p)\) or \(y_{max}=y(w_p) > y(w_{p+2})\). (See Fig. 7(e).)
(2) \(y_{max}=y(w_p) = y(w_{p+2})\). (See Fig. 7(g).)
Case 3: \(k=l\).(See Fig. 5(f).)
Let \(U_l=\{u_1,u_2, \cdots ,u_r\}\), and let \(C_o(G_{l-1})=(w_1,w_2, \cdots ,w_f, \cdots ,w_t)\) be the outer cycle of \(G_{l-1}\) where \(w_1=a_3\) and \(w_f=a_1\). Let \(w_s^i\) be the smallest vertex of \(u_i \in U_l\), for each \(i=1,2, \cdots ,r\). For each \(i=1,2, \cdots ,r\), we set \(x(u_i)=x(w_s^i)\), as illustrated in Fig. 5(f).
We then explain how to decide \(y(U_l)\). Let \(y_{max}\) be the maximum value of y-coordinates of \(w_1,w_2, \cdots ,w_f\). We set \(y(U_l)=y_{max}+1\), as illustrated in Fig. 5(f).
The following lemmas are known for the drawing obtained by the algorithm.
Lemma 2: [16] Let \(\Pi=(U_1,U_2, \cdots ,U_l)\) be a 5-canonical decomposition of \(G\). Let \(1 \le k \le l-1\) and let \(C_o(G_k)=(w_1,w_2, \cdots ,w_f, \cdots ,w_t)\) be the outer cycle of \(G_k\) where \(w_1=a_3\) and \(w_f=a_1\). Then, for each index \(k\), \(1 \le k \le l-1\), the drawing of the path going clockwise on \(C_o(G_k)\) from \(w_1\) to \(w_f\) is x-monotone.
Lemma 3: [16] If \((u,v)\) is an edge in \(G\) and \(u \preceq v\), then the y-coordinates of vertices \(u\) and \(v\) decided by the algorithm satisfy \(y(u) \leq y(v)\).
Lemma 4: [16] Let \(\Pi=(U_1,U_2, \cdots ,U_l)\) be a 5-canonical decomposition of \(G\). Let \(2 \le k \le l\) and let \(w_p,w_{p+1}, \cdots ,w_q\) be the smaller neighbors of a vertex \(u \in U_k\). Then the following (a) and (b) hold:
(a) there is no index \(t\) such that \(p < t < q\) and \(w_{t-1} \prec w_t \succ w_{t+1}\); and
(b) \(w_p \succeq w_{p+1} \succeq \cdots \succeq w_m \preceq \cdots \preceq w_q\), and \(y(w_p) \geq y(w_{p+1}) \geq \cdots \geq y(w_m) \leq \cdots \leq y(w_q)\) where \(w_m\) is the smallest vertex among \(w_p, w_{p+1}, \cdots ,w_q\).
Lemma 5: [16] Let \(G\) be a five-connected internally triangulated plane graph having at least five vertices on \(C_o(G)\). Then the algorithm finds a grid drawing of \(G\) on a \(W \times H\) grid such that \(W + H \leq n-2\) in linear time.
4. Proof for Open RI-Drawing
In this section, we prove the grid drawing of a 5-connected plane graph \(G\) found by the algorithm in [16] is an open RI-drawing of \(G\).
We have the following lemmas.
Lemma 6: Let \(D(G_k)\), \(2 \le k \le l\) be the drawing of \(G_k\) obtained by the algorithm in [16], and let \(e\) be an edge in \(G_k\) but not in \(G_{k-1}\). Then there is no vertex in an open rectangle-of-influence of \(e\) in \(D(G_k)\).
Proof: Suppose for a contradiction that there is a vertex in the open rectangle-of-influence of \(e\) in \(D(G_k)\). We only consider the case where \(U_k\) satisfies either condition (a) of (co4) or (co2), because the other case is identical. Let \(U_k=\{u\}\). Let \(C_o(G_{k-1})=(w_1,w_2, \cdots ,w_f, \cdots ,w_t)\) be the outer cycle of \(G_{k-1}\) where \(w_1=a_3\) and \(w_f=a_1\), let \(w_p,w_{p+1}, \cdots ,w_q\) be the smaller neighbors of \(u\), and let \(w_s\) be the smallest vertex among \(w_{p+1},w_{p+2}, \cdots ,w_{q-1}\). We may assume without loss of generality that \(e\) is drawn as a line segment of positive slope as illustrated in Fig. 8. The edge \(e\) divides the open rectangle of \(e\) into two right-angled triangles, the upper triangle and the lower one.
 |
Fig. 8 Illustrations for Lemma 6. |
We first consider the case where there is a vertex in the upper triangle of the open rectangle of \(e\). In this case, one can observe that there is a vertex \(w_r\) on \(C_o(G_{k-1})\), such that \(x(w_r) \geq x(w_{r+1})\), as illustrated in Fig. 8(a), and hence contrary to Lemma 2.
We then consider the case where there is a vertex in the lower triangle of the open rectangle of \(e\). In this case, one can observe that there is a vertex \(w_r\) on \(C_o(G_{k-1})\), such that \(y(w_{r-1}) < y(w_{r}) \geq \cdots > y(w_s)\), as illustrated in Fig. 8(b), and hence contray to Lemma 4(b).\(\tag*{◻}\)
Lemma 7: Let \(D(G_k)\), \(1 \le k \le l-1\) be the drawing obtained by the algorithm in [16]. Let \(C_o(G_k)=(w'_1(=a_3),w'_2, \cdots ,w'_{f'-1}, w'_{f'}(=a_1),w'_{f'+1}, \cdots ,w'_{t'})\), let \(b\) is any index, \(1 \leq b \leq f'\), and let \(e\) be an edge in \(G_k\). If \(D(G_k)\) is an open RI-drawing of \(G_k\) and we execute an arbitrary number of operations \(shift(w_b)\), then we again obtain an open RI-drawing of \(G_k\).
Proof: The proof is by induction on \(k\). For \(D(G_1)\) the lemma is obvious. So suppose that it holds for \(D(G_{k-1})\), \(k \geq 2\). Let \(C_o(G_{k-1})=(w_1(=a_3),w_2, \cdots ,w_{f-1}, w_f(=a_1),w_{f+1}, \cdots ,w_t)\) as in the algorithm. We are about to add \(U_k\) to \(D(G_{k-1})\). One can observe that \(D(G_k)\) is an open RI-drawing of \(G_k\) by induction and by Lemma 6. Let \(w_p\) and \(w_q\) be the leftmost and rightmost neighbors of \(U_k\) in \(C_o(G_{k-1})\). Let \(U_k=\{u_1,u_2, \cdots ,u_r\}\), \(r \geq 1\), Then the outer cycle of \(G_k\) is \(C_o(G_k)=w'_1,w'_2, \cdots ,w'_{t'}\) where
| \[\begin{aligned} &\!\!\!\!\! t'=t+ \gamma,\\ &\!\!\!\!\! \gamma=r-q+p+1, \end{aligned}\] |
and
| \[\begin{equation*} w'_i=\left \{ \notag \begin{aligned} w_i & ~{\rm if}~ 1 \leq i \leq p;\\ u_{i-p} & ~{\rm if}~ p+1 \leq i \leq p+r;\\ w_{i-\gamma} & ~{\rm if}~ p+r+1 \leq i \leq t'. \end{aligned} \right. \end{equation*}\] |
If \(b \geq p+r+2\), then \(shift(w_b)\) in \(D(G_k)\) is equivalent to \(shift(w_b)\) in \(D(G_{k-1})\) since \(U_k\) does not move, and the lemma follows directly by induction. If \(b \leq p\), then the lemma also follows from the inductive assumption, since \(U_k\) shifts rigidly with the rest of the graph.
Let us assume now that \(U_k\) satisfies condition (co4)(a), that is, \(U_k=\{u_1\}\). The proof when \(U_k\) satisfies condition (co4)(b) is similar. Then it suffices to consider the two cases \(b=p+1\) and \(b=p+2\): \(w_b=u_1\) and \(w_b=w_q\).
Executing \(shift(w_q)\) in \(D(G_k)\) is equivalent to \(shift(w_q)\) in \(D(G_{k-1})\), but in \(D(G_k)\) it also stretches the edge \((u_1,w_q)\). In the triangle \(w_{q-1}u_1w_q\), by Lemmas 2 and 3, we have \(x(u_1),x(w_{q-1}) < x(w_q)\) and \(y(w_{q-1}) \leq y(w_q) \leq y(u_1)\), so the lemma follows by induction.
Executing \(shift(u_1)\) in \(D(G_k)\) is equivalent to \(shift(w_{p+1})\) in \(D(G_{k-1})\) and increasing \(x(u_1)\) by 1, but in \(D(G_k)\) it also stretches the edge \((u_1,w_p)\). In the triangle \(w_{p+1}u_1w_p\), by Lemmas 2 and 3, we have \(x(u_1),x(w_{p+1}) > x(w_p)\) and \(y(w_{p+1}) \leq y(w_p) \leq y(u_1)\), so the lemma follows by induction.\(\tag*{◻}\)
By lemmas 5, 6 and 7, we have the following main theorem.
Theorem 1: Let \(G\) be a five-connected internally triangulated plane graph having at least five vertices on \(C_o(G)\). Then the algorithm in [16] finds an open RI-drawing of \(G\) on a \(W \times H\) grid such that \(W + H \leq n-2\) in linear time.
5. Conclusions
In this paper, we show that any given 5-connected plane graph \(G\) has an open RI-drawing on an integer grid such that \(W + H \leq n-2\) if \(G\) has five or more vertices on the outer face. It will be conjectured that every 5-connected plane graph \(G\) has an open RI-drawing on a \(\lfloor 2n/5\rfloor \times \lfloor 2n/5\rfloor\) grid, that is \(W + H \leq 4n/5\), but it is left as an open problem.
Acknowledgments
This work was supported by Competitive Research Funds for Fukushima University Faculty (24FD001).
We would like to thank Yuto Onodeta for valuable discussion.
References
[1] T.C. Biedl, A. Bretscher, and H. Meijer, “Rectangle of influence drawings of graphs without filled 3-cycles,” Proc. Graph Drawing’99 (GD99), LNCS 1731, pp.359-368, 2000.
CrossRef
[2] G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis, Graph Drawing, Prentice Hall, NJ, 1998.
[3] M. Chrobak and G. Kant, “Convex grid drawings of 3-connected planar graphs,” International Journal of Computational Geometry and Applications, vol.7, no.3, pp.211-223, 1997.
CrossRef
[4] M. Chrobak and S. Nakano, “Minimum-width grid drawings of plane graphs,” Computational Geometry: Theory and Applications, vol.11, no.1, pp.29-54, 1998.
CrossRef
[5] M. Chrobak and T. Payne, “A linear-time algorithm for drawing planar graphs on a grid,” Information Processing Letters, vol.54, no.4, pp.241-246, 1995.
CrossRef
[6] H. de Fraysseix, J. Pach, and R. Pollack, “How to draw a planar graph on a grid,” Combinatorica, vol.10, pp.41-51, 1990.
CrossRef
[7] A. Garg and A. Rusu, “Straight-line drawings of binary trees with linear area and arbitrary aspect ratio,” Journal of Graph Algorithms and Applications, vol.8, no.2, pp.135-160, 2004.
CrossRef
[8] A. Garg and A. Rusu, “Area-efficient planar straight-line drawings of outerplanar graphs,” Discrete Applied Mathematics, vol.155, no.9, pp.1116-1140, 2007.
CrossRef
[9] X. He, “Grid embedding of 4-connected plane graphs,” Discrete Comput. Geom., vol.17, pp.339-358, 1997.
CrossRef
[10] J.W. Jaromczyk and G.T. Toussaint, “Relative neighborhood graphs and their relatives,” Proc. IEEE, vol.80, no.9, pp.1502-1517, 1992.
CrossRef
[11] G. Kant, “Drawing planar graphs using the canonical ordering,” Algorithmica, vol.16, pp.4-32, 1996.
CrossRef
[12] M.R. Karim, M.J. Aahman and M.S. Rahman, “Straight-line grid drawings of label-constrained outerplanar graphs with O(n log n) area,” Journal of Graph Algorithms and Applications, vol.15, no.3, pp.437-456, 2011.
CrossRef
[13] M.R. Karim and M.S. Rahman, “On a class of planar graphs with straight-line grid drawings on linear area,” Journal of Graph Algorithms and Applications, vol.13, no.2, pp.153-177, 2009.
CrossRef
[14] G. Kant and X. He, “Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems,” Theoretical Computer Science, vol.172, nos.1-2, pp.175-193, 1997.
CrossRef
[15] G. Liotta, A. Lubiw, H. Meijer, and S.H. Whitesides, “The rectangle of influence drawability problem,” Comput. Geom. Theory and Applications, vol.10, no.1, pp.1-22, 1998.
CrossRef
[16] K. Miura “Grid drawings of five-connected plane graphs,” IEICE Trans. Fundamentals, vol.E105-A, no.9, pp.1228-1234, Sept. 2022.
CrossRef
[17] K. Miura, T. Matsuno, and T. Nishizeki, “Open rectangle-of-influence drawings of inner triangulated plane graphs,” Discrete Comput. Geom., vol.41, pp.643-670, 2009.
CrossRef
[18] K. Miura and T. Nishizeki, “Rectangle-of-influence drawings of four-connected plane graphs,” Proc. Information Visualisation 2005, Asia-Pacific Symposium on Information Visualisation (APVIS2005), vol.45, pp.71-76, 2005.
[19] K. Miura, S. Nakano, and T. Nishizeki, “Grid drawings of 4-connected plane graphs,” Discrete Comput. Geom., vol.26, no.1, pp.73-87, 2001.
CrossRef
[20] S. Nagai and S. Nakano, “A linear-time algorithm for five-partitioning five-connected internally triangulated plane graphs,” IEICE Trans. Fundamentals, vol.E84-A, no.9, pp.2330-2337, Sept. 2001.
CrossRef
[21] S. Nagai and S. Nakano, “A linear-time algorithm to find independent spanning trees in maximal planar graphs,” IEICE Trans. Fundamentals, vol.E84-A, no.5, pp.1102-1109, May 2001.
[22] T. Nishizeki and M.S. Rahman, Planar Graph Drawing, World Scientific, Singapore, 2004.
CrossRef
[23] W. Schnyder, “Embedding planar graphs on the grid,” Proc. 1st Annual ACM-SIAM Symp. on Discrete Algorithms, San Francisco, pp.138-148, 1990.
[24] R. Tamassia, Handbook of Graph Drawing and Visualization, Chapman & Hall/CRC, Boca Raton, 2013.
CrossRef
Authors
Fukushima University
received the B.E., M.E., and Ph.D. degrees from Tohoku University, Sendai, Japan, in 1996, 1998 and 2001, respectively. He was a research associate at Tohoku University during 2001-2004. He joined the Faculty of Symbiotic Systems Science, Fukushima University, as an Associate Professor in 2005, then in 2022 was promoted to Professor. His research interests are in the field of algorithms for planar graphs and graph drawing. He is a member of IEICE and IPSJ.
 |
