• 検索結果がありません。

KazuyukiMiura AkiraKamada TakaoNishizeki ConvexGridDrawingsofPlaneGraphswithRectangularContours JournalofGraphAlgorithmsandApplications

N/A
N/A
Protected

Academic year: 2022

シェア "KazuyukiMiura AkiraKamada TakaoNishizeki ConvexGridDrawingsofPlaneGraphswithRectangularContours JournalofGraphAlgorithmsandApplications"

Copied!
28
0
0

読み込み中.... (全文を見る)

全文

(1)

Convex Grid Drawings of Plane Graphs with Rectangular Contours

Kazuyuki Miura

1

Akira Kamada

2

Takao Nishizeki

2

1Faculty of Symbiotic Systems Science, Fukushima University, Fukushima 960-1296, Japan.

2Graduate School of Information Sciences, Tohoku University, Sendai 980-8579, Japan.

Abstract

In a convex drawing of a plane graph, all edges are drawn as straight- line segments without any edge-intersection and all facial cycles are drawn as convex polygons. In a convex grid drawing, all vertices are put on grid points. A plane graphGhas a convex drawing if and only ifGis internally triconnected, and an internally triconnected plane graphGhas a convex grid drawing on an (n−1)×(n−1) grid if eitherGis triconnected or the triconnected component decomposition treeT(G) ofG has two or three leaves, where n is the number of vertices in G. In this paper, we show that an internally triconnected plane graphGhas a convex grid drawing on a 2n×n2 grid ifT(G) has exactly four leaves. We also present an algorithm to find such a drawing in linear time. Our convex grid drawing has a rectangular contour, while most of the known algorithms produce grid drawings having triangular contours.

Submitted:

August 2007

Reviewed:

June 2008

Revised:

July 2008

Accepted:

July 2008

Final:

July 2008 Published:

October 2008 Article type:

Regular Paper

Communicated by:

X. He

E-mail addresses: miura@sss.fukushima-u.ac.jp(Kazuyuki Miura) kamada@nishizeki.ecei.tohoku.ac.jp (Akira Kamada) nishi@ecei.tohoku.ac.jp(Takao Nishizeki)

(2)

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 [13]. The most typical drawing of a plane graph is astraight line drawing, in which all edges are drawn as straight line segments without any edge-intersection. A straight line drawing is called a convex drawing if every facial cycle is drawn as a convex polygon. One can find a convex drawing of a plane graphGin linear time ifGhas one [3, 4, 13].

A straight line drawing of a plane graph is called agrid drawingif all vertices are put on grid points of integer coordinates. This paper deals with aconvex grid drawingof a plane graph. Throughout the paper we assume for simplicity that every vertex of a plane graphGhas degree three or more. ThenGhas a convex drawing if and only ifGis “internally triconnected,” that is,Gcan be extended to a triconnected graph by adding a vertex in the outer face and joining it to all outer vertices [11, 15]. One may thus assume without loss of generality that G is internally triconnected. If either G is triconnected or the “triconnected component decomposition tree”T(G) ofGhas two or three leaves, thenGhas a convex grid drawing on an (n−1)×(n−1) grid and such a drawing can be found in linear time, wherenis the number of vertices ofG[1, 2, 10]. However, it has not been known whetherGhas a convex grid drawing of polynomial size ifT(G) has four or more leaves. Figure 1(a) depicts an internally triconnected plane graphG, Fig. 2(b) the triconnected components ofG, and Fig. 2(c) the triconnected component decomposition tree T(G) of G, which has four leaves l1, l2, l3and l4.

In this paper, we show that an internally triconnected plane graph G has a convex grid drawing on a 2n×n2 grid if T(G) has exactly four leaves, and present an algorithm to find such a drawing in linear time. The algorithm is outlined as follows: we first divide a plane graphGinto an upper subgraphGu

and a lower subgraphGd as illustrated in Fig. 1(b) for the graph in Fig. 1(a);

we then construct “inner” convex grid drawings ofGu and Gd by a so-called shift method as illustrated in Figs. 1(c) and (d); we finally extend these two drawings to a convex grid drawing of G as illustrated in Fig. 1(e). This is the first algorithm that finds a convex grid drawing of such a plane graph G in a grid of polynomial size. The size 2n×n2 of our convex grid drawing is larger than the size (n−1)×(n−1) of a convex grid drawing of a triconnected plane graph obtained by previously known algorithms [1, 2, 5]. It is known that every triconnected plane graph has a “strict convex grid drawing” of size O(n7/3)×O(n7/3) in which all facial cycles are drawn as strictly convex polygons [14]. It is also known that every internally triconnected plane graph has a grid drawing of size (n−1)×(n−2) in which all inner facial cycles are drawn as convex polygons although the outer facial cycle is not necessarily drawn as a convex polygon [2, 13]. Our convex grid drawing has a rectangular contour, while most of the previously known algorithms except those in [8, 12] produce a grid drawing having a triangular contour [1, 2, 5, 6, 10, 17].

The remainder of the paper is organized as follows. In Section 2 we give

(3)

(a) (b)

(d)

(e) (c)

a 1

a 2

a 3 a

4 s

1 , s

8 s

2 s

3

s 4

s 5

s 6 s

7

a 3 a

4 s

1 , s

8

s 4

s 5

s 6 s

7 a

1

a 2 s

2 s

3

G d G

u

G G

u and G

d

a 3 a

4

v r

v l a

1

= v r

a 2

v l

D u

D d

P u

P d

a 3 a

4

W(D)

W(D)+1 H(D

u )

H(D) a

1

a 2

H(D d

)

D

Figure 1: (a) Plane graphG, (b) upper subgraph Gu and lower subgraph Gd, (c) inner convex drawingDuofGu, (d) inner convex drawingDdofGd, and (e) convex grid drawingD ofG.

(4)

(a) (b)

(c)

a 3 a

1

a 2

a 4 s

1 , s

8

s

2 s

3

s 4

s 5

s 6 s

7

u 4 l

1

l 2

l 3 l

4

Figure 2: (a) Split components of the graph G in Fig. 1(a), (b) triconnected components ofG, and (c) decomposition treeT(G).

(5)

some definitions and known lemmas. In Section 3 we explain an algorithm for GuandGd. In Section 4 we present our convex grid drawing algorithm. Finally we conclude in Section 5. An early version of the paper was presented at [9].

2 Preliminaries

In this section, we give some definitions and known lemmas.

AW×H integer gridconsists ofW+ 1 regular vertical grid lines andH+ 1 regular horizontal grid lines, and has a rectangular contour. We callW and H thewidthandheight of the integer grid, respectively. We denote byW(D) the width of a minimum integer grid enclosing a grid drawingDof a graph, and by H(D) the height ofD.

We denote byG= (V, E) an undirected connected simple graph with vertex set V and edge setE. We often denote the set of vertices of Gby V(G) and the set of edges byE(G). Throughout the paper we denote bynthe number of vertices inG. An edge joining verticesuandv is denoted by (u, v). Thedegree of a vertexv in Gis the number of neighbors ofv inG.

A plane graphGdivides the plane into connected regions, calledfaces. The infinite face is called anouter face, and the others are calledinner faces. The boundary of a face is called afacial cycle. A cycle is represented by a clockwise sequence of the vertices in the cycle. We denote byFo(G) the outer facial cycle ofG. A vertex onFo(G) is called anouter vertex, while a vertex not onFo(G) is called aninner vertex. In a convex drawing of a plane graphG, all facial cycles must be drawn as convex polygons. The convex polygonal drawing ofFo(G) is called theouter polygon. We call a vertex of a polygon anapexin order to avoid the confusion with a vertex of a graph.

We call a vertexv of a connected graphGa cut vertexif its removal from Gresults in a disconnected graph, that is,G−vis not connected. A connected graphGisbiconnectedifGhas no cut vertex. We call a pair{u, v}of vertices in a biconnected graphG a separation pair if its removal from G results in a disconnected graph, that is,G− {u, v} is not connected. A biconnected graph G is triconnected if G has no separation pair. A biconnected plane graph G is internally triconnected if, for any separation pair {u, v} of G, both u and v are outer vertices and each connected component of G− {u, v} contains an outer vertex. In other words,Gis internally triconnected if and only if it can be extended to a triconnected graph by adding a vertex in the outer face and joining it to all outer vertices. If a biconnected plane graphGis not internally triconnected, thenGhas a separation pair{u, v}as illustrated in Figs. 3(a)–(c) and a “split graph”H contains an inner vertex other thanuandv; in Fig. 3(a) bothuand v are inner vertices, in Fig. 3(b) one ofuand v, sayv, is an inner vertex, and in Fig. 3(c) both u and v are outer vertices but a split graph H contains no outer vertex other thanuandv.

LetG= (V, E) be a biconnected graph, and let{u, v}be a separation pair ofG. Then,Ghas two subgraphs G1 = (V1, E1) andG2 = (V2, E2) satisfying the following two conditions.

(6)

u

v

u

v H

H

H

v u

(a) (b) (c)

Figure 3: Biconnected plane graphs which are not internally triconnected.

(a)V =V1S

V2, V1T

V2={u, v}; and (b)E=E1

SE2,E1

TE2 =∅,|E1| ≥2,|E2| ≥2.

For a separation pair{u, v}ofG,G1= (V1, E1+(u, v)) andG2= (V2, E2+(u, v)) are called the split graphs of G with respect to {u, v}. The new edges (u, v) added to G1 and G2 are called the virtual edges. Even if G has no multiple edges,G1 andG2 may have. Dividing a graphGinto two split graphsG1 and G2 is calledsplitting. Reassembling the two split graphs G1 and G2 into Gis called merging. Merging is the inverse of splitting. Suppose that a graph G is split, the split graphs are split, and so on, until no more splits are possible, as illustrated in Fig. 2(a) for the graph in Fig. 1(a) where virtual edges are drawn by dotted lines. The graphs constructed in this way are called thesplit componentsofG. The graph in Fig. 1(a) has eleven split components illustrated in Fig. 2(a). The split components are of three types: a triconnected graph; a triple bond (i.e. a set of three multiple edges); and a triangle (i.e. a cycle of length three). The triconnected components of G are obtained from the split components ofGby merging triple bonds into a bond and triangles into a ring, as far as possible, where abondis a set of multiple edges and aringis a cycle.

Thus the triconnected components ofGare of three types:

(a) a triconnected graph;

(b) a bond; and (c) a ring.

The split components of G are not necessarily unique, but the triconnected components ofGare unique [7, 16]. Two triangles in Fig. 2(a) are merged into a single ring, and hence the graph in Fig. 1(a) has ten triconnected components as illustrated in Fig. 2(b).

LetT(G) be a tree such that each node corresponds to a triconnected com- ponentHi of Gand there is an edge (Hi, Hj),i6=j, inT(G) if and only ifHi

andHj are triconnected components with respect to the same separation pair, as illustrated in Fig. 2(c). We callT(G) a triconnected component decomposi- tion tree or simply a decomposition tree of G [7, 16]. We denote by ℓ(G) the number of leaves ofT(G). Then ℓ(G) = 4 for the graph Gin Fig. 1(a). (See Fig. 2(c).) IfGis triconnected, thenT(G) consists of a single isolated node and henceℓ(G) = 1.

(7)

The following three lemmas are known.

Lemma 1 [7] A decomposition treeT(G)of a graph Gcan be found in linear time.

Lemma 2 [11] Let G be a biconnected plane graph in which every vertex has degree three or more. Then the following three statements are equivalent to each other:

(a)Ghas a convex drawing;

(b) Gis internally triconnected; and

(c) both vertices of every separation pair are outer vertices, and a node of the decomposition treeT(G)of Ghas degree two if it is a bond.

Lemma 3 [11] If a plane graph G has a convex drawing D, then the number of apices of the outer polygon ofD is no less thanmax{3, ℓ(G)}, and there is a convex drawing ofGwhose outer polygon has exactlymax{3, ℓ(G)} apices.

SinceGis an internally triconnected simple graph and every vertex ofGhas degree three or more, by Lemma 2 every leaf ofT(G) is a triconnected graph.

Lemmas 2 and 3 imply that ifT(G) has exactly four leaves, that is, ℓ(G) = 4 then the outer polygon of every convex drawing ofG must have four or more apices. Our algorithm obtains a convex grid drawing ofGwhose outer polygon is a rectangle and hence has exactly four apices, as illustrated in Fig. 1(e).

In Section 3, we will present an algorithm to draw the upper subgraphGu

and the lower subgraphGd. (See Fig. 1(b).) The algorithm uses the follow- ing “canonical decomposition.” LetG = (V, E) be an internally triconnected plane graph, and let V = {v1, v2,· · ·, vn}. Let v1, v2 and vn be three arbi- trary outer vertices appearing counterclockwise on Fo(G) in this order. We may assume that v1 and v2 are consecutive on Fo(G); otherwise, add a vir- tual edge (v1, v2) to the original graph, and letG be the resulting graph. Let Π = (U1, U2,· · · , Um) be an ordered partition of V into nonempty subsets U1, U2,· · ·, Um, whereU1S

U2S

· · ·S

Um=V andUiT

Uj=∅for any indicesi andj, 1≤i < j≤m. We denote byGk, 1≤k≤m, the subgraph ofGinduced byU1S

U2S· · ·S

Uk, and denote byGk, 0≤k≤m−1, the subgraph ofGin- duced byUk+1S

Uk+2S· · ·S

Um. Clearly,Gk =G−Uk+1S

Uk+2S· · ·S Um

and G = Gm = G0. We say that Π is a canonical decomposition of G (with respect to vertices v1, v2 and vn) if the following three conditions (cd1)–(cd3) hold:

(cd1) Um={vn}, and U1 consists of all the vertices on the inner facial cycle containing edge (v1, v2).

(cd2) For each indexk, 1≤k≤m,Gk is internally triconnected.

(cd3) For each indexk, 2≤k≤m, all the vertices inUk are outer vertices of Gk, and

(8)

(a) if|Uk|= 1, then the vertex inUk has two or more neighbors inGk−1

and has one or more neighbors inGk whenk < m, as illustrated in Fig. 4(a); and

(b) if|Uk| ≥2, then each vertex inUk has exactly two neighbors inGk, and has one or more neighbors inGk, as illustrated in Fig. 4(b).

U k

U k

G k-1

G k-1

(a) (b)

Figure 4: (a) GraphsGk for which|Uk|= 1 and (b) |Uk| ≥2.

Although the definition of a canonical decomposition above is slightly dif- ferent from the one given in [2], they are effectively equivalent with each other.

A canonical decomposition Π = (U1, U2,· · ·, U11) with respect to verticesv1, v2

andvn of the graph in Fig. 5(a) is illustrated in Fig. 5(b).

The following lemma is known.

Lemma 4 [10] Assume that G is an internally triconnected plane graph and ℓ(G)≤3. Then one can find a canonical decomposition Π of Gin linear time ifv1, v2 andvn are chosen as follows.

Case 1: ℓ(G) = 3.

In this case, from each of the three triconnected components corresponding to leaves ofT(G), we choose an arbitrary outer vertex of Gwhich is not a vertex of the separation pair of the component.

Case 2: ℓ(G) = 2.

In this case, we choose two vertices from the two leaves of T(G), similarly to Case 1 above. We choose an arbitrary outer vertex ofGother than them as the third one.

Case 3: ℓ(G) = 1.

In this case, G is triconnected. We choose three arbitrary outer vertices of G.

One can easily observe that Lemma 4 holds even if exactly one of the outer vertices has degree two and the vertex is chosen asvn.

3 Pentagonal drawing

LetGbe a plane graph having a canonical decomposition Π = (U1, U2,· · ·, Um) with respect to verticesv1, v2andvn, as illustrated in Fig. 5(b). In this section,

(9)

(b)

(c) (a)

(d) U

5

U 1 U

2 U

3

U 4

U 8 U

7 U

6

U 9

U 10 U

11

v r

v 2

= a 3 v

1

= a 4 v

l

D m v

n

= w

D m-1

a 3 a

4

v r

v l

v 2

= a 3 v

1

= a 4 v

l

= s

1 v

r

= s 4 v

n

= w

G(= G d

) V

l

V r

'

Figure 5: (a) An internally triconnected plane graphG(=Gd), (b) a canonical decomposition Π of G, (c) a drawing Dm−1 of Gm−1, and (d) a pentagonal drawingDmofG.

we present a linear-time algorithm, called a pentagonal drawing algorithm, to find a convex grid drawing ofGwith a pentagonal outer polygon, as illustrated in Fig. 5(d). The algorithm is based on the so-called shift methods given by Chrobak and Kant [2] and de Fraysseixet al. [5], and will be used by our convex grid drawing algorithm to draw the lower subgraphGdand the upper subgraph Gu ofGin Sections 4.2 and 4.3, respectively.

Letvl be an arbitrary vertex on the path going from v1 tovn clockwise on Fo(G), and letvr(6=vl) be an arbitrary vertex on the path going fromv2 tovn

counterclockwise onFo(G), as illustrated in Fig. 5(a). Let Vl be the set of all vertices on the path going fromv1tovlclockwise onFo(G), and letVrbe the set of all vertices on the path going fromv2 tovrcounterclockwise onFo(G). Our algorithm obtains a convex grid drawing ofGwhose outer polygon is a pentagon with apicesv1, v2, vr, vn andvl, as illustrated in Fig. 5(d). The pentagon has a shape similar to a baseball home plate; the sidev1v2 is horizontal, and the two sidesv1vlandv2vrare vertical and contain all vertices inVlandVr, respectively.

(10)

(a) (b)

v r

= v 2 v

1 v

l

= v n

v l

= v 1

v r

= v 2 v

n

Figure 6: (a) Convex grid drawings ofGin Fig. 5(a) for the case wherevl=v1

andvr=v2, and (b) for the case wherevl=vn andvr=v2.

w 1

= v 1 w

f

w 2

G k-1

w g

w t

= v 2

Figure 7: DrawingDk−1 of graphGk−1.

However,vl may bev1 orvn, andvr may bev2 orvn, and hence the pentagon may degenerate into a right-angled isosceles triangle as illustrated in Figs. 6(a) and (b).

For each k, 2 ≤ k ≤ m, let Fo(Gk−1) = w1, w2,· · ·, wt, where w1 = v1, wt = v2, and w1, w2,· · · , wt appear clockwise on Fo(Gk−1) in this order, as illustrated in Fig. 7.

We first obtain a drawingD1of the subgraphG1ofGinduced by all vertices in U1. Let Fo(G1) = w1, w2,· · ·, wt, w1 = v1, andwt = v2. We drawG1 as illustrated in Fig. 8, depending on whether (v1, v2) is a real edge or not,w2∈Vl

or not, andwt−1∈Vr or not. (See Appendix for the details.) Initialize:

Case 1: v1andv2are adjacent in an original graphG, that is, (v1, v2) is a real

(11)

edge.

In this case we draw G1 as a trapezoid such that the bottom side has length 2t−2 and the two sides other than the top and bottom have slope

±1 or±∞.

Ifw2∈Vl andwt−16∈Vr, then drawG1as in Fig. 8(a);

Ifw26∈Vl andwt−1∈Vr, then drawG1as in Fig. 8(b);

Ifw2∈Vl andwt−1∈Vr, then drawG1as in Fig. 8(c);

Ifw26∈Vl andwt−16∈Vr, then drawG1as in Fig. 8(d);

Case 2: Otherwise, that is, (v1, v2) is a virtual edge.

DrawG1on a horizontal line segment of length 2t−2, as in Fig. 8(e).

(b)

(e)

(a) (c) (d)

w t w

1 w

2

w t

= v 2 w

1

= v 1 w

2

w t w

1 w

2

w t w

1 w

2

w 1

w 2

w t w

t

-

1 wt

-

1

w

t

-

1 wt

-

1

w t

-

1

Figure 8: DrawingsD1ofG1 (a)–(d) for Cases 1 and (e) for Case 2.

We then extend a drawing Dk−1 of Gk−1 to a drawingDk of Gk for each index k, 2≤ k ≤m. Let Fo(Gk−1) =w1, w2,· · · , wt, w1 =v1, wt =v2, and Uk={u1, u2,· · · , ur}. By the condition (cd3) of a canonical decomposition, one may assume that the verticesu1, u2,· · ·, urinUkappear clockwise onFo(Gk) in this order and that the first vertexu1 and the last oneurinUk have neighbors inGk−1. (See Fig. 4.) Letwp be the leftmost neighbor ofu1, that is,wpis the neighbor ofu1in Gk having the smallest indexp, and letwq be the rightmost neighbor ofur, as illustrated in Fig. 9.

Letwf be the vertex with the maximum indexf among all the verticeswi, 1 ≤ i ≤t, on Fo(Gk−1) that are contained in Vl. Let wg be the vertex with the minimum index g among all the vertices wi, 1≤i ≤t, on Fo(Gk−1) that are contained inVr. Of course, 1≤f < g≤t. We denote by 6 wi the interior angle of apexwi of the outer polygon ofDk−1. We callwi a convex apexof the polygon if6 wi <180. We denote the current position of a vertexv byP(v);

P(v) is expressed by its x- and y-coordinates as (x(v), y(v)). Assume that a drawingDk−1 ofGk−1 satisfies the following six conditions (sh1)–(sh6).

(12)

(sh1)P(w1) = (0,0) andP(wt) = (2nk−1−2,0), wherenk−1=|V(Gk−1)|.

(sh2)x(w1) =x(w2) =· · ·=x(wf), x(wf)< x(wf+1)<· · ·< x(wg), x(wg) = x(wg+1) =· · ·=x(wt), wherex(wi) is thex-coordinate ofwi.

(sh3) Every edge (wi, wi+1),f ≤i≤g−1, has slope−1,0, or 1.

(sh4) The Manhattan distance between any two grid points wi and wj, f ≤ i < j≤g, is an even number.

(sh5) Every inner face ofGk−1 is drawn as a convex polygon.

(sh6) Vertexwi,f+ 1≤i≤g−1, has one or more neighbors inGk−1 ifwi is a convex apex.

IndeedD1 satisfies the six conditions above. We extendDk−1toDk so that Dk satisfies them, as follows.

Before installingUk to Dk−1, we shift (move to the left or right) some ver- tices of Gk−1 as illustrated in Figs. 9(a)–(d). We first shift w1, w2,· · ·, wp of Gk−1 and some inner vertices ofGk to the left by distance|Uk|, and then shift wq, wq+1,· · ·, wtofGk−1and some inner vertices ofGkto the right by distance

|Uk|. After the operation, we shift all vertices ofGk−1 to the right by distance

|Uk|so thatP(w1) = (0,0). See Appendix for the details.

(d) (c)

(b) (a)

w p

w q

w 1

w t G

k-1

G k-1

G k-1

G k-1

w g

w f

w p

w q

w 1

w t w

g

w f

w p

w q

w 1

w t w

g

w f

w p

w q

w 1

w t w

g

w f u

1

u 1

u 1

u 2

u r

u 1

u 2

u r

Figure 9: (a) GraphsGk−1 for Case|Uk|= 1, (b) for Case|Uk| ≥2, (c) graphs Gk for Case|Uk|= 1, and (d) for Case|Uk| ≥2.

Then, we installUk toDk−1 as follows. (See Appendix for the details.)

(13)

Install Uk: Case 1: |Uk|= 1.

Ifu1∈Vl, then put the vertexu1 inUk abovewf =wp so that the edge (u1, wq) has slope−1, as in Fig. 10(a);

Ifu1∈Vr, then putu1abovewg=wq so that the edge (wp, u1) has slope +1, as in Fig. 10(b);

If u1 6∈ Vl and u1 6∈ Vr, then put u1 on a grid point so that the edge (wp, u1) has slope +1 and the edge (u1, wq) has slope−1, as in Fig. 10(c);

(a) (b) (c)

u 1

w q

u 1

w p

u 1

w

p w

q

w 1

w t

w 1

w t

w 1

w t G

k-1 Gk-1 Gk-1

w p

= w f

w g

w f

w q

= w g

w f

w g

Figure 10: InstallingUk ={u1}to Dk−1. Case 2: |Uk| ≥2.

Case (a): u1∈Vl andur6∈Vr.

Ify(wq)−y(wp) is an odd number≥1, then put the verticesu1, u2,

· · ·, urinUkon a horizontal line ofy-coordinate max{y(wp), y(wq)}+

1, as in Fig. 11(a);

Otherwise, put the vertices inUkon a horizontal line ofy-coordinate max{y(wp), y(wq)}+ 2, as in Fig. 11(a);

Case (b): u16∈Vl andur∈Vr.

If y(wp)−y(wq) is an odd number ≥ 1, then put the vertices in Uk on a horizontal line of y-coordinate max{y(wp), y(wq)}+ 1, as in Fig. 11(b);

Otherwise, put the vertices inUkon a horizontal line ofy-coordinate max{y(wp), y(wq)}+ 2, as in Fig. 11(b);

Case (c): u1∈Vl andur∈Vr.

Put the vertices inUkon a horizontal line ofy-coordinate max{y(wp), y(wq)}+ 1, as in Fig. 11(c);

Case (d): u16∈Vl andur6∈Vr.

Put the vertices inUkon a horizontal line ofy-coordinate max{y(wp), y(wq)}+ 1, as in Fig. 11(d).

(14)

(c) (b) (a)

(d) (b ) (a ) w

p

w q

u 1

u r

w p

w q u

1

u r

w q u

1

u r

w p

u 1

u r

w p

w q

u 1

u w r

p

w q w

1

w t

w 1

w t

w 1

w t

w 1

w t

w 1

w t u

1

u r

w p

w q

w 1

w t

'

'

G k

-

1

G k

-

1

G k

-

1

G k

-

1

G k

-

1

G k

-

1

Figure 11: InstallingUk={u1, u2,· · ·, ur}, r≥2, toDk−1.

Clearly, the drawingDkofGkextended fromDk−1satisfies conditions (sh1), (sh2) and (sh3). One can prove similarly as in [5] that Dk satisfies condition (sh4), and prove similarly as in [2] thatDk satisfies conditions (sh5) and (sh6).

One can easily show that the pentagonal drawing algorithm takes linear time.

We finally consider the widthW =W(D) and heightH =H(D) of the final drawingD=DmofG=Gm.

For eachk, 1≤k≤m, the drawingDk ofGk satisfies conditions (sh1) and (sh2), and hence we have

W(Dk) = 2nk−2 wherenk=|V(Gk)|. We thus have

W(D) =W(Dm) = 2n−2.

Sincen1≥3, we have

H(D1)≤4≤n21−n1−2.

(15)

One can easily observe from Figs. 10 and 11 thatH(Dk)≤H(Dk−1) +W(Dk) for eachk, 2≤k≤m. Notingnk=nk−1+|Uk| ≥nk−1+ 1, one can inductively prove that

H(Dk)≤n2k−nk−2.

Therefore we have

H(D)≤n2−n−2.

We thus have the following lemma.

Lemma 5 For a plane graph G having a canonical decomposition Π = (U1, U2,· · · , Um) with respect to v1, v2 and vn, the pentagonal drawing algorithm yields a convex grid drawing of G on a W ×H grid with W = 2n−2 and H ≤ n2−n−2 in linear time. Furthermore, W(Dm−1) = 2nm−1−2 and H(Dm−1)≤n2m−1−nm−1−2.

If vl =v1 and vr =v2, then the outer pentagon degenerates into a right- angled isosceles triangle with6 v1vnv2 = 90 and H =n−1, as illustrated in Fig. 6(a). Such a grid drawing is effectively the same as the one obtained by the algorithm in [5].

If vl = vn and vr =v2, then the outer pentagon degenerates into a right- angled isosceles triangle with6 vnv1v2 = 90 and H = 2n−2, as illustrated in Fig. 6(b). Such a convex grid drawing is effectively the same as the one obtained by the algorithm in [2].

Thus our pentagonal drawing algorithm is an extension of both the straight- line drawing algorithm in [5] and the convex grid drawing algorithm in [2].

Let Π = (U1, U2,· · · , Um) be a canonical decomposition of the plane graph Gin Fig. 12(a). Then|U1|= 3, |U2|=|U3|=· · ·=|Um|= 1, and m=n−2.

Letnbe an odd number,vl=vn, andvr=vn−1. Then, the pentagonal drawing algorithm drawsGk as illustrated in Fig. 12(b), and the widthW = 2n−2 and heightH =n2−n−2 ofGattains the bounds in Lemma 5.

4 Convex grid drawing algorithm

In this section we present a linear algorithm to find a convex grid drawingDof an internally triconnected plane graphG whose decomposition treeT(G) has exactly four leaves. Such a graphG does not have a canonical decomposition, and hence none of the algorithms in [1], [2], [6] and [10] and the pentagonal drawing algorithm in Section 3 can find a convex grid drawing of G. Our algorithm draws the outer facial cycle Fo(G) as a rectangle as illustrated in Fig. 1(e). The algorithm first dividesGinto an upper subgraphGuand a lower subgraph Gd as illustrated in Fig. 1(b), then draws Gu and Gd by using the pentagonal drawing algorithm as illustrated in Figs. 1(c) and (d), and finally combine these two drawings to a convex grid drawing of G as illustrated in Fig. 1(e).

(16)

(a) (b) U

3

U 1

U 2

U 4

v n

v 1

v 2

v n - 1

G 3 G

1

G 2

G 4

Figure 12: (a) A graphG, and (b) drawings ofG1, G2, G3 andG4.

4.1 Division

We first explain how to divideGintoGuandGd. (See Figs. 1(a) and (b).) One may assume that the four leavesl1, l2, l3andl4ofT(G) appear clockwise inT(G) in this order, as illustrated in Fig. 13. Clearly, either exactly one node u4ofT(G) has degree four and each of the other non-leaf nodes has degree two as illustrated in Fig. 13(a), or exactly two nodesul3and ur3 have degree three and each of the other non-leaf nodes has degree two as illustrated in Fig. 13(b).

One may assume that, in Fig. 13(b), nodeul3 is arranged to the left and node ur3 to the right.

(a) (b)

u 4 l

1

l 2

l 3 l

4

u r 3 l

1 l

2

l 3 l

4 u l 3

Figure 13: Decomposition treesT(G) (a) having a node of degree four and (b) having two nodes of degree three.

Since each vertex ofGis assumed to have degree three or more, all the four leaves ofT(G) are triconnected graphs. Moreover, according to Lemma 2, every triconnected component of G having degree three or four in T(G) is either a triconnected graph or a ring, while every bond has degree two in T(G). Thus there are the following six cases (a)–(f) to consider.

(a) Nodeu4is a triconnected graph as illustrated in Fig. 14(a);

(17)

(b) Nodeu4is a ring as illustrated in Fig. 14(b);

(c) Both of nodesul3andur3are triconnected graphs as illustrated in Fig. 14(c);

(d) Node ul3 is a triconnected graph and ur3 is a ring, as illustrated in Fig. 14(d);

(e) Nodeul3is a ring andur3is a triconnected graph, as illustrated in Fig. 14(e);

(f) Both of nodesul3 andur3 are rings as illustrated in Fig. 14(f).

(a) (b)

(e) (f)

(c) (d)

u 4 s

1

s 1

s 1 s

4

s 4

s 4

s 8

s 8

s 8

s 5

s 5 s

5 u

4

u l 3

u r 3

u l 3

u r 3

u l 3

u r 3 u

l 3

u r 3 s

2 s

3

s 5

s 6 s

7 s

8

s 1

s 4 s

2 s

3

s 6 s

7

s

2 s

3

s 5

s 6 s

7 s

8

s 4 s

2 s

3

s 6 s

7 s

8

s 1

s

2 s

3

s 5

s 6 s

7

s 1

s 4 s

2 s

3

s 6 s

7 a

1

a 2

a 3 a

4

a 1

a 2

a 3 a

4

a 1

a 2

a 3 a

4

a 1

a 2

a 3 a

4

a 1

a 2

a 3 a

4

a 1

a 2

a 3 a

4

Figure 14: GraphG, decomposition and pathP for Cases (a)–(f).

As the four apices of the rectangular contour of G, we choose four outer verticesai, 1 ≤i ≤4, of G; letai be an arbitrary outer vertex in the compo- nent corresponding to leafli that is not a vertex of the separation pair of the component. The four verticesa1, a2, a3 and a4 appear clockwise on Fo(G) in this order as illustrated in Fig. 1(a).

We then choose eight vertices s1, s2,· · ·, s8 from the outer vertices of the components u4, ul3 and ur3. Among these outer vertices, let s1 be the vertex that one encounters first when one traversesFo(G) counterclockwise from vertex a1, and let s2be the vertex that one encounters first when one traversesFo(G)

(18)

clockwise from a1, as illustrated in Figs. 1(a) and 14. (Thus, {s1, s2} is a separation pair ofG, and corresponds either to the edge ofT(G) which is incident to nodeu4 and lies on the path between u4 and leafl1 inT(G) or to the edge ofT(G) which is incident to nodeul3 and lies on the path betweenul3andl1.) Similarly, we chooses3 and s4 for a2, s5 and s6 for a3, and s7 and s8 fora4. Possiblys2=s3,s4=s5,s6=s7, and s8=s1.

We then show how to divideGinto Gu andGd.

a 1

a 2

a a 3

4 s

1 , s

8 s

2

s 3

s 4

s 5

s s 6

7

G

Figure 15: GraphG.

Consider all the inner faces of Gthat contain one or more vertices on the path going froma1 to a2 clockwise onFo(G). (All these faces for the graphG in Fig. 1(a) are shaded in Fig. 15.) LetG be the subgraph ofGinduced by all the vertices on these faces. Then Fo(G) is a simple cycle, which is drawn by thick lines in Fig. 15. Clearly,Fo(G) contains vertices s1 and s4 in all Cases (a)–(f), contains vertexs8 in Cases (b), (e) and (f), and contains vertex s5 in Cases (b), (d) and (f). For Cases (a) and (c), letP be the path going froms1

to s4 counterclockwise onFo(G), as illustrated in Figs. 1(a), 14(a) and 14(c) whereP is drawn by thick lines. For Cases (b) and (f), letP be the path going froms8 to s5counterclockwise onFo(G), as illustrated in Figs. 14(b) and (f).

For Case (d), letP be the path going froms1tos5counterclockwise onFo(G), as illustrated in Fig. 14(d). For Case (e), letP be the path going froms8to s4

counterclockwise onFo(G), as illustrated in Fig. 14(e).

Let Gd be the subgraph of G induced by all the vertices on P or below P, and letGu be the subgraph of Gobtained by deleting all vertices inGd as illustrated in Fig. 1(b). For every edgeeof Gthat is contained neither in Gu

nor inGd, one of the ends of eis onFo(Gu) and the other is on Fo(Gd). Let ndbe the number of vertices ofGd, and letnube the number of vertices ofGu. Thennd+nu=n.

4.2 Drawing of G

d

We now explain how to drawGd.

(19)

LetGdbe a graph obtained fromGby contracting all the vertices ofGuto a single vertexw, as illustrated in Fig. 5(a) for the graphGin Fig. 1(a). Then clearly Gd is biconnected. We now claim that Gd is internally triconnected.

Suppose for a contradiction that Gd is not internally triconnected. Then Gd has a separation pair {u, v} for which there is a split graph H illustrated in Figs. 3(a), (b) and (c). SinceG is internally triconnected and all the vertices of Gd except w are vertices ofG, one may assume that u= w and H has a structure in Fig. 3(b) or (c). We consider only the case whereGdhas a structure in Fig. 3(b), because one can similarly give a proof for the other case whereGd has a structure in Fig. 3(c). ThenGdhas a structure as illustrated in Fig. 16(a), and henceGhas a structure illustrated in Fig. 16(b) or (c). IfGhas a structure in Fig. 16(b), thenGis not internally triconnected, a contradiction. IfGhas a structure in Fig. 16(c), then all the vertices above the pathP (drawn by thick lines in Fig. 16(c)) should be contracted to a single vertexw inGd and hence Gd does not have a structure in Fig. 16(a), a contradiction.

(a)

(b) (c)

G d

' G G

w

P

a 3 a

4

a 3 a

4

a 2 a

1

a 3 a

4

a 2 a

1

Figure 16: (a) Graph Gd having a structure in Fig. 3(b), (b) G which is not internally triconnected, and (c)Gand the pathP.

The decomposition tree T(Gd) of Gd has exactly two leaves l3 andl4, and a3anda4 are contained in the triconnected graphs corresponding to the leaves and are not vertices of the separation pairs. Every vertex of Gd other thanw has degree three or more, andw has degree two or more inGd. Therefore,Gd

has a canonical decomposition Π = (U1, U2,· · · , Um) with respect toa4,a3and w, as illustrated in Fig. 5(b), whereUm={w}. Letvl be the vertex preceding w clockwise on the outer faceFo(Gd), and letvr be the vertex succeeding w, as illustrated in Fig. 5(a). We obtain a pentagonal drawingDmof Gd by the algorithm in Section 3, as illustrated in Fig. 5(d). The drawingDm−1 ofGm−1

induced by U1S

U2S· · ·S

Um−1 is our drawing Dd of Gd(= Gm−1). (See Figs. 1(d) and 5(c).) By Lemma 5, we have W(Dd) = 2nd−2 and H(Dd)≤ n2d−nd−2.

4.3 Drawing of G

u

We now explain how to draw Gu. Let Gu be a graph obtained from G by contracting all the vertices ofGdto a single vertexw, as illustrated in Fig. 17(a).

(20)

Similarly toGd, Gu has a canonical decomposition Π = (U1, U2,· · · , Um) with respect to a2, a1 and w, as illustrated in Fig. 17(b), where Um ={w}. Let vr be the vertex succeeding w clockwise on the outer face Fo(Gu), and let vl be the vertex precedingw, as illustrated in Fig. 17(a). We rotateGu by 180 as illustrated in Fig. 17(b). We then obtain a drawingDm−1 ofGu(= Gm−1) by the algorithm in Section 3, as illustrated in Fig. 17(c) where the clockwise path froma2to vl and the clockwise path fromvr toa1 onFo(Gu) are drawn as vertical line segments. (The path from vr to a1 degenerates into a single path in Fig. 17(c) since vr=a1.) We finally rotate it to obtain a drawingDu

ofGu, as illustrated in Fig. 1(c). By Lemma 5, we haveW(Du) = 2nu−2 and H(Du)≤n2u−nu−2.

(b)

(c) (a)

a 1=

v r

a 2 s

2

s 3

w

v l

U 3

U 2

U 8

U 4

U 1 U

7 U

6

U 5 w

a 2

a 1

G u

a 1

= v r a

2 v

l

D u

' '

'

'

'

'

'

Figure 17: (a) GraphGu, (b) a canonical decomposition ofGu, and (c) a drawing DuofGu.

4.4 Drawing of G

If W(Dd) 6= W(Du) as in Figs. 1(c) and (d), then we widen the narrow one of Dd and Du by the shift operation in Section 3 so that both have the same width. (SinceW(Du) = W(Dd)−2 for Du in Fig. 1(c) andDd in Fig. 1(d), we widenDuby shifting vertexa1to the left by two as illustrated in Fig. 1(e).) We may thus assume thatW(Dd) =W(Du) = max{2nd−2,2nu−2}. Since we combine the two drawingsDd andDuof the same width to a drawingD of

(21)

G, we have

W(D) = max{2nd−2,2nu−2}<2n.

We arrange Dd and Du so that y(a3) = y(a4) = 0 and y(a1) = y(a2) = H(Dd)+H(Du)+W(D)+ 1, as illustrated in Fig. 1(e). Noting thatnd+nu=n andnd, nu≥5, we have

H(D) = H(Dd) +H(Du) +W(D) + 1

< (n2d−nd−2) + (n2u−nu−2) + 2n+ 1

< n2.

We finally draw, by straight line segment, all the edges of Gthat are con- tained in neither Gu nor Gd. This completes the grid drawing D of G. (see Fig. 1(e).)

4.5 Validity of drawing algorithm

In this section, we show that the drawing D obtained above is a convex grid drawing ofG. Since bothDdandDu satisfy condition (sh5), every inner facial cycle ofGdandGuis drawn as a convex polygon in D. Therefore, it suffices to show that the straight line drawings of the edges not contained inGu andGd

do not introduce any edge-intersection and that all the faces newly created by these edges are convex polygons.

Since Dd satisfies condition (sh3), the absolute value of the slope of every edge on the pathPdgoing fromvltovrclockwise onFo(Gd) is less than or equal to 1. The path Pd is drawn by thick lines in Fig. 1(d). (Note thatDdmay be widen by the shift operation ifW(Dd)< W(Du).) Similarly, the absolute value of the slope of every edge on the pathPugoing from vr tovl counterclockwise onFo(Gu) is less than or equal to 1. SinceH(D) =H(Dd)+H(Du)+W(D)+1, the absolute value of the slope of every straight line segment that connects a vertex inGuand a vertex inGdis larger than 1. Therefore, all the outer vertices ofGd onPd are visible from all the outer vertices of Gu on Pu. Furthermore, Gis a plane graph. Thus the addition of all the edges not contained inGuand Gd does not introduce any edge-intersection.

SinceDdsatisfies condition (sh6), every convex apex of the outer polygon of GdonPdhas one or more neighbors inGu. Similarly, every convex apex of the outer polygon ofGu onPu has one or more neighbors in Gd. Therefore, every interior angle of a newly formed face is smaller than 180. Thus all the inner faces ofGnot contained inGuandGd are convex polygons inD.

Thus, D is a convex grid drawing of G. Clearly the algorithm takes linear time. We thus have the following main theorem.

Theorem 1 Assume that G is an internally triconnected plane graph, every vertex ofGhas degree three or more, and the triconnected component decompo- sition treeT(G)has exactly four leaves. Then our algorithm finds a convex grid drawing ofGon a 2n×n2 grid in linear time.

(22)

We finally remark that the grid size is improved to 2n×4nfor the case where either the node u4 of degree four in T(G) is a ring as illustrated in Fig. 14(b) orT(G) has two nodes of degree three as illustrated in Figs. 14(c)–(f). In such a case, the pathsP and hencePd, drawn by thick lines in Figs. 1(a), 1(d) and 14(b)–(f), pass through the outer verticess6and s7. Clearlyy(s6) =y(s7) = 0 in Dd. Therefore, condition (sh3) implies that H(Dd) < W(Dd) = 2nd−2.

Similarly we haveH(Du)< W(Du) = 2nu−2. Thus we have H(D) =H(Dd) +H(Du) +W(D) + 1<4n.

5 Conclusions

In this paper, we showed that every internally triconnected plane graphGwhose decomposition treeT(G) has exactly four leaves has a convex grid drawing on a 2n×n2 grid, and we present a linear algorithm to find such a drawing. This is the first algorithm that finds a convex grid drawing of such a graphGon a grid of polynomial size. The remaining problem is to obtain an algorithm for an internally triconnected plane graph whose decomposition tree has five or more leaves.

Acknowledgments

The authors would like to thank the referees for helpful comments.

(23)

References

[1] N. Bonichon, S. Felsner and M. Mosbah, Convex drawings of 3-connected plane graphs, Algorithmica, 47, 4, pp. 399–420, 2007.

[2] M. Chrobak and G. Kant, Convex grid drawings of 3-connected planar graphs,International Journal of Computational Geometry and Applications, 7, pp. 211–223, 1997.

[3] N. Chiba, K. Onoguchi and T. Nishizeki, Drawing planar graphs nicely, Acta Inform., 22, pp. 187–201, 1985.

[4] N. Chiba, T. Yamanouchi and T. Nishizeki, Linear algorithms for convex drawings of planar graphs, inProgress in Graph Theory, J. A. Bondy and U.

S. R. Murty (Eds.), Academic Press, pp. 153–173, 1984.

[5] H. de Fraysseix, J. Pach and R. Pollack,How to draw a planar graph on a grid, Combinatorica, 10, pp. 41–51, 1990.

[6] S. Felsner,Convex drawings of plane graphs and the order of dimension of 3-polytopes, Order, 18, pp. 19–37, 2001.

[7] J. E. Hopcroft and R. E. Tarjan,Dividing a graph into triconnected com- ponents,SIAM J. Compt.2, 3, pp. 135–158, 1973.

[8] ´E. Fusy, Transversal structures on triangulations, with application to straight-line drawing, Proc. of GD2005, LNCS 3843 pp. 177–188, 2006.

[9] A. Kamada, K. Miura and T. Nishizeki, Convex grid drawings of plane graphs with rectangular contours -Extended Abstract-,Proc. of ISAAC 2006, Springer Lect. Notes in Computer Science, 4288, pp. 131–140, 2006.

[10] K. Miura, M. Azuma and T. Nishizeki,Canonical decomposition, realizer, Schnyder labeling and orderly spanning trees of plane graphs,International Journal of Foundations of Computer Science, 16, 1, pp. 117–141, 2005.

[11] K. Miura, M. Azuma and T. Nishizeki, Convex drawings of plane graphs of minimum outer apices,International Journal of Foundations of Computer Science, 17, 5, pp. 1115–1127, 2006.

[12] K. Miura, S. Nakano and T. Nishizeki, Convex grid drawings of four- connected plane graphs, International Journal of Foundations of Computer Science, 17, 5, pp. 1032–1060, 2006.

[13] T. Nishizeki and M. S. Rahman, Planar Graph Drawing, World Scientific, Singapore, 2004.

[14] G. Rote,Strictly convex drawings of planar graphs,Proc. of 16th Ann. ACM- SIAM Symp. on Discrete Algorithms, pp. 728–734, 2005.

(24)

[15] C. Thomassen,Planarity and duality of finite and infinite graphs,J. Com- binatorial Theory, Series B, 29, pp. 244–271, 1980.

[16] W. T. Tutte, Connectivity in Graphs, University of Tronto Press, Tronto, 1966.

[17] W. Schnyder and W. Trotter,Convex drawings of planar graphs,Abstracts of the AMS 13, 5, 92T-05-135, 1992.

参照

関連したドキュメント

In particular, we show that the strong convergence implies the weak convergence and disprove the converse through a counter-example, by invoking an analogue of Parseval’s identity

The following variation was considered by Beineke and Schwenk [1] and also by Irving [5]: for 1 ≤ m ≤ n, the bipartite Ramsey number R(m, n) is the smallest integer r such that

For a positive definite fundamental tensor all known examples of Osserman algebraic curvature tensors have a typical structure.. They can be produced from a metric tensor and a

As we saw before, the first important object for computing the Gr¨ obner region is the convex hull of a set of n &gt; 2 points, which is the frontier of N ew(f ).. The basic

We can formulate this as an extremal result in two ways: First, for every graph G, among all bipartite graphs with a given number of edges, it is the graph consisting of disjoint

Due to Kondratiev [12], one of the appropriate functional spaces for the boundary value problems of the type (1.4) are the weighted Sobolev space V β l,2.. Such spaces can be defined

, n is called a recursive tree if the vertex labelled 1 is the root and, for all 2 ≤ k ≤ n, the sequence of vertex labels in the path from the root to k is increasing (Stanley

A set S of lines is universal for drawing planar graphs with n vertices if every planar graph G with n vertices can be drawn on S such that each vertex of G is drawn as a point on