Augmenting Outerplanar Graphs

Augmenting Outerplanar Graphs

JOURNAL OF ALGORITHMS ARTICLE NO. 21, 1]25 Ž1996. 0034 Augmenting Outerplanar Graphs* Goos Kant Department of Computer Science, Utrecht Uni¨ ersity...

219KB Sizes 4 Downloads 87 Views

JOURNAL OF ALGORITHMS ARTICLE NO.

21, 1]25 Ž1996.

0034

Augmenting Outerplanar Graphs* Goos Kant Department of Computer Science, Utrecht Uni¨ ersity, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands Received March 9, 1992

In this paper, we show that for outerplanar graphs G the problem of augmenting G by adding a minimum number of edges such that the augmented graph G9 is planar and bridge-connected, biconnected, or triconnected can be solved in linear time and space. It is also shown that augmenting a biconnected outerplanar graph to a maximal outerplanar graph while minimizing the maximum degree can be achieved in polynomial time. These augmentation problems arise in the area of drawing outerplanar graphs. Q 1996 Academic Press, Inc.

1. INTRODUCTION The graph drawing problem becomes a core field in the area of graph algorithms, due to the large number of applications. New workshops and overviews are devoted to this subject w2x. Several different aesthetic criteria are described, developed and implemented in real-life applications. A huge number of drawing algorithms require as input a planar graph, i.e., a graph which can be drawn without any pair of crossing edges. In particular, several of these algorithms require as additional constraint that the graph is biconnected, triconnected or triangulated. In this paper, we focus our attention on outerplanar graphs, that are planar graphs which can be drawn planarly with all vertices occuring on one face, the outerface. In the literature, several algorithms are described especially for outerplanar graphs, because of the nice properties of this class of graphs. In particular, very recently drawing algorithms are presented for outerplanar graphs Že.g., see w10, 20]22x.. We will describe them briefly in Section 3. The typical problem which arises now is: what to do when the graph does not admit the additional connectivity requirement? The solution we * This work was supported by the ESPRIT II Basic Research Actions Program of the EC under Contracts 3075 and 7141 ŽProjects ALCOM I and II.. 1 0196-6774r96 $18.00 Copyright Q 1996 by Academic Press, Inc. All rights of reproduction in any form reserved.

2

GOOS KANT

present is to add a small number of edges to the graph to fulfill this requirement. If the augmented graph is still Žouter.planar, then we can use one of the Žouter.planar drawing algorithms. The added edges can be a disadvantage for the specific properties of the drawing algorithm. As an example, the drawing algorithm of Tutte w28x draws a triconnected planar graph with interior convex faces. Deleting the added edges in the drawing leads to a number of non-convex faces. Hence the aim is to add as few extra edges as possible. Nowadays, the area of graph augmentation problems is an increasing field of study. Augmentation algorithms are developed with respect to vertex-connectivity w6, 7, 12, 14, 15, 26, 29x and edge-connectivity w8, 9, 24, 30, 32x. Among these papers, optimal linear time algorithms are given for augmenting graphs with respect to bridge-connectivity w6x, biconnectivity w14, 26x, and triconnectivity w15, 31x. The connectivity constraint is not only an important argument for graph drawing, but also for the robustness in communication networks w29, 30, 32x. However, these papers do not deal with the additional constraint of being planar. In w16x, Kant considers the problem of augmenting a planar graph such that the augmented planar graph is biconnected and still planar. It is proved in w16x that the problem of finding the minimum number of edges such that the augmented graph is biconnected and planar is NP-complete. An O Ž n ? a Ž n, m.. time approximation algorithm is presented in w16x as well, adding at most two times the minimum number of edges to obtain a biconnected planar graph. A linear time approximation algorithm for the planar triconnectivity problem is presented by Kant w16x, adding at most 3r2 times the minimum number of edges. Kant and Bodlaender w18x present an algorithm for triangulating planar graphs such that the maximum degree is at most a constant from existential lower bounds. In this paper, we first present a linear time algorithm for biconnecting an outerplanar graph, such that the augmented graph is still outerplanar. The number of added edges is at most b y 1, where b is the number of biconnected components of the graph. We also present a connected outerplanar graph, requiring b y 1 additional edges to obtain a biconnected outerplanar graph. The major part of this paper deals with the problem of augmenting an outerplanar graph by adding edges such that the augmented outerplanar graph is planar and bridge-connected, biconnected, or triconnected. The algorithms we present are conceptually simple, easy to implement and have a linear running time. They serve as a starting point for drawing them by the well-known graph drawing algorithms Žsee w2x for an overview.. The algorithm for biconnecting an outerplanar graph to a planar graph is actually a modification of the algorithm of Rosenthal and Goldner w26x and

AUGMENTING OUTERPLANAR GRAPHS

3

Hsu and Ramachandran w14x. They present an augmentation algorithm for biconnecting general graphs without the planarity constraint. ŽIn particular, the algorithm of w26x is simplified in w14x. Also an error in the algorithm of w26x is corrected in w14x.. The interesting part of our modification is that it can be used to triconnect outerplanar graphs. In all cases, the number of added edges is minimum, and is equal to the number of edges in the nonplanar case. A last problem considered in this paper is the augmentation of an outerplanar graph to a maximal outerplanar graph, while minimizing the maximum degree. The additional requirement for the degree is important with respect to the outerplanar drawing algorithm, described by Malitz and Papakostas w21x Žsee also w10x.. A polynomial time algorithm for this problem is presented, based on dynamic programming. The paper is organized as follows: In Section 2, the necessary definitions are given. In Section 3, two drawing algorithms for outerplanar graphs are presented, and the augmentation algorithm while preserving outerplanarity. In Sections 4, 5, and 6, the planar augmentation algorithms for outerplanar graphs to meet bridge-connectivity, biconnectivity, and triconnectivity constraints, respectively, are presented. In Section 7, the augmentation algorithm is presented to obtain a maximal outerplanar graph while minimizing the maximum degree.

2. DEFINITIONS AND PRELIMINARIES We start with presenting several standard definitions used in this paper. Let G s Ž V, E . be an undirected graph with < V < s n vertices and < E < s m edges. G is connected if there is a path between every pair of vertices. If ¨ is a vertex of G such that G y  ¨ 4 is disconnected, then ¨ is called a cut¨ ertex. If Ž x, y . is an edge such that G9 s Ž V, E y Ž x, y .. is disconnected, then Ž x, y . is called a bridge. If G is connected, has G 3 vertices and contains no cutvertices, it is called biconnected. If G is connected, has G 3 vertices and contains no bridges, it is called bridge-connected. If G is connected, has G 4 vertices and the deletion of any two vertices with incident edges preserves the connectivity, then G is called triconnected. A tree is an undirected, connected, acyclic graph. A graph is called planar if it can be drawn in the plane such that there is no pair of crossing edges. A graph is called outerplanar if it can be drawn as a planar graph with all vertices occuring on one face, called the outerface. The other faces are called interior faces. A triangulated or maximal outerplanar graph or map is an outerplanar graph, where every interior face is a triangle. Adding any edge to a mop destroys the outerplanarity. Notice that an outerplanar graph G cannot be tricon-

4

GOOS KANT

nected, because deleting any pair of vertices u, ¨ , sharing an interior face and not consecutive on the outerface disconnects the graph. Central to the algorithms is the concept of the block graph of G, denoted by bcŽ G . Žcf. Harary w11x.: each biconnected component Žalso called block . is represented by a B-node and each cutvertex of G is represented by a C-node of bcŽ G .. Two nodes u, ¨ of bcŽ G . are adjacent if and only if the corresponding cutvertex of u in G is contained in the corresponding block of ¨ in G or vice versa. It can easily be shown that bcŽ G . is always a forest. It is known as the BC-tree of G when G is connected. Every path in bcŽ G . contains alternating B- and C-nodes. A pendant or pendant block is a block which contains exactly one cutvertex. pŽ ¨ . denotes the number of pendant blocks connected at ¨ . p is the total number of pendant blocks in G, i.e., the number of leaves in bcŽ G .. q denotes the number of isolated nodes in bcŽ G .. dŽ ¨ . denotes the number of components of G y  ¨ 4 . Each component of G y  ¨ 4 is called a ¨ -block. If G is a tree then for all ¨ , dŽ ¨ . s deg Ž ¨ .. d s max ¨ g V  dŽ ¨ .4 . For a set of vertices V s  ¨ 1 , . . . , ¨ l 4 in tree T we call w the least common ancestor, if w is on every path from a vertex ¨ g V to the root and from all these candidates, the path from w to the root has maximum length. We denote w by w s LCA ¨ 1 , . . . , ¨ l 4 . If G is disconnected we connect G by applying the following technique of Eswaran and Tarjan w6x: Let bcŽ G . have t trees, numbered from 1 to t. For each i with 1 F i F 2 t, let ¨ Ž i . be a set of vertices of bcŽ G . such that: 1. ¨ Ž2 i y 1. and ¨ Ž2 i . are each a pendant or an isolated vertex in the ith tree of bcŽ G ., for each 1 F i F t. 2. ¨ Ž2 i y 1. s ¨ Ž2 i . if and only if the ith tree of bcŽ G . is an isolated vertex. It easily follows that bcŽ G . j Ž ¨ Ž2 i ., ¨ Ž2 i q 1.. N 1 F i - t 4 is a tree having p9 s p q 2 q y 2Ž t y 1. pendants and no isolated vertices w6x. We call this algorithm CONNECTŽ G . throughout the paper. Assume now that G is connected, and let TB C be the corresponding BC-tree. We assume that the cutvertices c1 , . . . , c k connected at a certain B-node b in TB C , appear in the order they occur on the outerface of the corresponding block B of G. This means that in TB C the order of the children of every B-node is fixed and for a C-node, any order of the children is allowed. Constructing a fixed TB C can be done in the similar way as constructing a normal TB C Že.g., by the linear time algorithm of Tarjan w27x.. In Fig. 1, an outerplanar graph G and the corresponding BC-tree TB C is given.

AUGMENTING OUTERPLANAR GRAPHS

5

FIG. 1. Example of a graph and its BC-tree Žfrom w14x..

3. DRAWING AND AUGMENTING OUTERPLANAR GRAPHS 3.1. Drawing Outerplanar Graphs Outerplanar graphs are an interesting subclass of planar graphs, because all vertices share one face w23x. Therefore specific drawing techniques for outerplanar graphs are developed Že.g., see w10, 20]22x.. A straightforward way is to place all vertices on the corner points of a regular n-gon in clockwise order around the face Žassumed the outerplanar is biconnected.. This leads to a planar convex drawing where the smallest angle formed by two edges incident on the same vertice is O Ž1rn. Žthis is called the angular resolution.. The ratio between the length of the longest and smallest edge can be O Ž n.. In the case of maximal outerplanar graphs, elaborated drawing algorithms are described w21, 10x. The algorithm of w21x starts with drawing a face F, say with vertices u, ¨ , w, which has at least one edge, say Ž u, ¨ ., on the outerface. It draws Ž u, ¨ . horizontally and draws w above Ž u, ¨ . such that the length of the edges Ž u, w . and Ž ¨ , w . are equal and / ¨ uw s / u¨ w. From Ž u, w . and Ž ¨ , w . the remaining faces of the outerplanar graph are drawn recursively Žsee Fig. 2.. The angular resolution is pr2Ž d q 2., but the ratio between the longest and smallest edge can be O Ž2 n ..

FIG. 2. Drawing an outerplanar graph.

6

GOOS KANT

By making extensive use of geometric considerations, Garg and Tamassia w10x were able to construct a drawing of a maximal outerplanar graph G with angular resolution prŽ d y 1.. This improves the lower bound of w21x by a factor of 2. The algorithm constructs a breadth-first search tree T of G and places the vertices on concentric circles in the drawing such that the vertices equidistant from the root of T are placed on the same circle. See w10x for more details. 3.2. Augmenting to Biconnected Outerplanar Graphs To biconnect an outerplanar graph, we can apply the following modification of the augmentation algorithm of Read w25x, presented in w16x. BICONNECTŽ G . construct a planar embedding of G such that all neighbors of ¨ i , belonging to the same block, appear consecutively in adjŽ ¨ i .; number the vertices ¨ i of G in depth-first order; for i [ 1 to n do if ¨ i is a cutvertex then let adjŽ ¨ i . s  u1 , . . . , u k 4 , with u1 and u k belonging to different blocks; for j [ 1 to k y 1 do if u j and u jq1 belong to different blocks then add an edge Ž u j , u jq1 . to G; if Ž ¨ i , u j . Žor Ž ¨ i , u jq1 .. was added to G then remove Ž ¨ i , u j . Žor Ž ¨ i , u jq1 ., resp.. from G rof rof; END BICONNECT THEOREM 3.1 w16x. The algorithm BICONNECT augments in linear time a planar graph to a biconnected planar graph, by adding at most b y 1 edges Ž b the number of blocks., and e¨ ery ¨ ertex recei¨ es at most two incident edges. THEOREM 3.2 w16x. If the input graph G is outerplanar, then the augmented graph obtained by BICONNECT is biconnected and outerplanar. Every biconnected graph is also bridge-connected, thus this algorithm can be used to bridge-connect G as well. In Fig. 3a, an illustration is given. In Fig. 3b, an outerplanar graph is given, requiring b y 1 extra edges to obtain a biconnected outerplanar graph. Biconnecting Žor bridge-connecting. G by a minimum number of edges while maintaining outerplanarity seems to be a much harder problem. Even for trees T this is not easy. For example, let T be a complete binary tree. Consider four consecutive leaves l 1 , l 2 , l 3 , l 4 of T. Let ¨ be the least

AUGMENTING OUTERPLANAR GRAPHS

7

FIG. 3. Biconnecting outerplanar graphs. Ža. Applying BICONNECT. Žb. Adding b y 1 edges to obtain biconnectivity.

common ancestor of them. Since ¨ must be part of the outerface after biconnecting, it follows that at most two of the following three edges can be added: Ž w, l 1 ., Ž l 2 , l 3 ., and Ž l 4 , w9., where w and w9 are arbitrary vertices outside l 1 , . . . , l 4 . This means that we get at least two edges between the vertices l 1 , . . . , l 4 , and at least one edge from l 1 , . . . , l 4 to a vertex outside l 1 , . . . , l 4 . This leads to the following theorem. THEOREM 3.3. At least uŽ8r5. p v edges are needed to make a complete binary tree with p lea¨ es bridge- or biconnected while maintaining outerplanarity. In Fig. 4a, it is shown how to make a complete binary tree biconnected, while adding Ž4r3. p y 1 edges. In Fig. 4b, it is shown how to make a complete 3-ary tree bridge-connected, by adding pr2 edges. These examples in combination with Theorem 3.3 show that there is no general lower bound in terms of p for the outerplanar augmentation problems.

FIG. 4. Augmenting while maintaining outerplanarity. Ža. Biconnecting a binary tree. Žb. Bridge-connecting a 3-ary tree.

8

GOOS KANT

4. BRIDGE-CONNECTIVITY In this section, we consider the problem how to add a minimum number of edges to an outerplanar graph G such that the augmented graph G9 is bridge-connected and planar. Eswaran and Tarjan considered the problem without the planarity constraint, and proved the following lower bound: THEOREM 4.1 w6x. At least q q u pr2v edges are needed to make G bridge-connected, where p is the number of pendants and q the number of isolated ¨ ertices in bcŽ G .. If G is disconnected, then we add q edges to make it connected by the algorithm CONNECTŽ G . Žsee Section 2.. Hence assume G is connected. Let TB C be the BC-tree. Bridge-connecting G means now bridge-connecting the fixed tree TB C with u pr2v edges. Root TB C at an arbitrary nonleaf B-node. We number the vertices of TB C as follows: We traverse the tree by a depth-first search traversal, and visit the children of a node from left to right for numbering, before numbering the node Žso-called postorder numbering .. Let ¨ 1 , . . . , ¨ n be the numbering of the vertices. Let ¨ Ž1., . . . , ¨ Ž p . be the leaves of TB C , numbered from left to right. The following lemma is easy to prove. LEMMA 4.2. The descendants of any node ha¨ e consecuti¨ e numbers in any postorder numbering. The idea of the algorithm is as follows: we visit the nodes in increasing postorder numbering. If ¨ i is a leaf ¨ Ž k . and k is odd, then we simply add an edge Ž ¨ Ž k y 1., ¨ Ž k ... If ¨ i is not a leaf, then we test whether there exists an augmenting edge Ž ¨ Ž a ., ¨ Ž b .., with ¨ Ž a . a descendant leaf of ¨ i and ¨ Ž b . not. If there is no such edge, then we change some added edges to obtain this. To this end a variable x is introduced, which increases monotone from 1 to p. We will prove that if ¨ Ž x . is a descendant leaf of ¨ i , then there exists an augmenting edge Ž ¨ Ž a ., ¨ Ž b .., with ¨ Ž a . a descendant leaf of ¨ i and ¨ Ž b . not. This precisely corresponds to the definition of the bridge-connectivity. The algorithm OUTERBRIDGECONNECT makes this idea more precise. ŽRecall the definition of LCA ¨ a , ¨ b 4 from Section 2.. OUTERBRIDGECONNECT Ž1. A [ B;  A becomes the set of augmenting edges.4 Ž2. x [ 1; Ž3. for i [ 2 to n do Ž4. if ¨ i is a leaf ¨ Ž k . then Ž5. if k is odd then A [ A j Ž ¨ Ž k y 1., ¨ Ž k ..4

AUGMENTING OUTERPLANAR GRAPHS

9

Ž6. else Ž7. let ¨ Ž j1 ., . . . , ¨ Ž jh . be the descendant leaves of ¨ i ; Ž8. if j1 is even and x - j1 then Ž9. A [ A y Ž ¨ Ž j1 ., ¨ Ž j2 ..4 j Ž ¨ Ž x ., ¨ Ž j1 ..4 ; x [ j2 Ž10. rof; Ž11. if x s 1 or x s p then A [ A j Ž ¨ Ž1., ¨ Ž p ..4 else Ž12. let Ž ¨ Ž1., ¨ Ž y .. g A; Ž13. if LCA ¨ Ž y ., ¨ Ž x .4 is an ancestor of LCA ¨ Ž x ., ¨ Ž p .4 then Ž14. A [ A y Ž ¨ Ž1., ¨ Ž y ..4 j Ž ¨ Ž y ., ¨ Ž x .., Ž ¨ Ž1., ¨ Ž p ..4 Ž15. else Ž16. A [ A j Ž ¨ Ž x ., ¨ Ž p ..4 ; END OUTERBRIDGECONNECT In Fig. 5, an example is given for the algorithm OUTERBRIDGECONNECT. It follows from the algorithm that < A < s u pr2v, but to prove that G indeed is bridge-connected and planar, we need the following lemma. LEMMA 4.3 w27x. Let G9 s Ž V, E j A., and let Ž ¨ , w . be an edge of G9. Then Ž ¨ , w . is a bridge of G9 if and only if ¨ is the parent of w in TB C and there is no edge Ž a , b . g A such that a is a descendant of w in TB C and b is not a descendant of w in TB C . LEMMA 4.4. If at some step during the algorithm, ¨ Ž x . is a descendant of w / ¨ 1 , then in the augmented graph w has a descendant leaf, which has an edge to a leaf, not a descendant of w. Proof. Let us call the added edges Ž ¨ Ž x ., ¨ Ž j1 .. of step Ž9. special. Notice that for every special edge Ž ¨ Ž a., ¨ Ž b .. a is odd and b is even, and the next special edge starts in ¨ Ž b q 1.. Consider a vertex w / ¨ 1 with

FIG. 5. Bridge-connecting an outerplanar graph. Ža. Numbering of the nodes and leaves. Žb. The bridge-connected augmentation.

10

GOOS KANT

descendant leaves ¨ Ž j1 ., . . . , ¨ Ž jh . from left to right. Assume first that after step Ž9. x ) j1 holds. If jh is odd then later the special edge Ž ¨ Ž jh ., ¨ Ž jh q 1.. is added, and ¨ Ž jh q 1. is not a descendant of w. If jh is even, then let Ž ¨ Ž a., ¨ Ž b .. be the special edge with b F jh as high as possible. When Ž ¨ Ž a., ¨ Ž b .. was added in a step Ž9., then x was set to b q 1. Since jh and b q 1 are both even it follows that x F jh . At the end x G jh q 2 holds, thus there exists a special edge Ž ¨ Ž a9., ¨ Ž b9.. with a9 F jh - b9. Assume now that after step Ž9. x F j1 holds. If x s 1 then p ) jh , and the edge Ž ¨ Ž x ., ¨ Ž p .. is added to A in step Ž11.. Otherwise let Ž ¨ Ž1., ¨ Ž y .. g A. Assume first that j1 F y. If jh s p then j1 ) 1 thus the added edge Ž ¨ Ž1., ¨ Ž y .. or Ž ¨ Ž1., ¨ Ž p .. satisfies the lemma. If p ) jh then the added edge Ž ¨ Ž x ., ¨ Ž p .. to A satisfies the lemma. If j1 ) y then if p ) jh then the edge Ž ¨ Ž y ., ¨ Ž x .. is added to A, otherwise the edge from ¨ Ž x . to ¨ Ž y . or ¨ Ž p . satisfies the lemma. LEMMA 4.5. G9 s Ž V, E j A. is bridge-connected. Proof. Let Ž ¨ , w . be any edge of G9 such that ¨ s parent Ž w . in TB C . Let the descendant leaves of w be ¨ Ž j1 ., . . . , ¨ Ž jh . from left to right. If j1 s 1 then initially ¨ Ž x . is a descendant of w and we can apply Lemma 4.4, so assume j1 ) 1. Every leaf gets an incident augmented edge, hence if j1 s jh then the lemma directly follows, thus assume jh ) j1. If j1 is odd, then the edge Ž ¨ Ž j1 y 1., ¨ Ž j1 .. is added in step Ž5.. If later Ž ¨ Ž j1 y 1., ¨ Ž j1 .. is removed, then x is set to j1 q 1 in step Ž9.. Hence in this case, ¨ Ž x . is a descendant of w, and we can apply Lemma 4.4. Otherwise, if j1 is even and x - j1 , then the edge Ž ¨ Ž x ., ¨ Ž j1 .. is added in step Ž9., and ¨ Ž x . is not a descendant of w. If x G j1 , then ¨ Ž x . is a descendant leaf of w, and we can apply Lemma 4.4. This completes the proof. Making G connected can be done in linear time by CONNECT. Constructing the BC-tree and the postordering of it requires linear time. At each nonleaf node ¨ we store a pointer to its leftmost leaf. Using this plus one pointer to leaf ¨ Ž x . the total required time is O Ž1. when visiting ¨ i in BRIDGECONNECT. After visting ¨ n , we have to decide whether LCA ¨ Ž y ., ¨ Ž x .4 is an ancestor of LCA ¨ Ž x ., ¨ Ž p .4 . We do this by looking whether there is a vertex ¨ 9 on the path between ¨ 1 and ¨ Ž p . such that for the leftmost leaf ¨ Ž z . of ¨ 9, y - z F x holds. LCA ¨ Ž y ., ¨ Ž x .4 is an ancestor of LCA ¨ Ž x ., ¨ Ž p .4 , if and only if there exists such a vertex ¨ 9. This leads to the main theorem of this section. THEOREM 4.6. The planar bridge-connecti¨ ity augmentation problem can be sol¨ ed in linear time and space for outerplanar graphs.

AUGMENTING OUTERPLANAR GRAPHS

11

5. BICONNECTIVITY In this section, we consider the problem of augmenting an outerplanar graph by adding a minimum number of edges such that the augmented graph is planar and biconnected. Hereto, we need the following definitions. DEFINITION 5.1 w14x. A node ¨ of TB C is called massi¨ e if and only if ¨ is a C-node with dŽ ¨ . y 1 ) u pr2v. A node ¨ of TB C is critical if and only if ¨ is a C-node with dŽ ¨ . y 1 s u pr2v. DEFINITION 5.2 w14x. TB C is critical if and only if there exists a critical C-node in TB C . TB C is balanced if and only if G has not a massive C-node. A graph G is balanced if and only if TB C is balanced. DEFINITION 5.3 ŽThe Leaf-Connecting Condition w14x.. Two leaves u1 and u 2 of TB C satisfy the leaf-connecting condition if and only if the path P from u1 to u 2 in TB C contains either Ž1. two nodes of degree more than 2 or Ž2. one B-node if degree more than 3. Some first observations concerning TB C are the following. LEMMA 5.1 w26x. There can be at most one massi¨ e node in TB C . If there is a massi¨ e node in TB C , then there is no critical node in TB C , and there can be at most two critical nodes in TB C , if p ) 2. LEMMA 5.2 w14x. Let u1 and u 2 be two lea¨ es of TB C satisfying the leaf-connecting condition Ž Definition 5.3.. Let a and b be non-cut¨ ertices in blocks of G represented by u1 and u 2 , respecti¨ ely. Let G9 be the graph obtained from G by adding an edge between a and b and let P represent the path between u1 and u 2 in TB C . The following three conditions are true: v

p9 s p y 2.

If ¨ is a C-node in P with degree greater than 2 in TB C , then the degree of ¨ decreases by 1 in TB C of G9. v

v

If ¨ is a C-node in P with degree equal to 2, then ¨ is eliminated in TB C

of G9. A lower bound for the number of required edges is gi¨ en by Eswaran and Tarjan. THEOREM 5.3 w6x. max d y 1, q q u pr2v4 edges are necessary to make G biconnected. We will show that we can achieve this bound for biconnecting outerplanar graphs as well. We follow the approach of Rosenthal and Goldner Žas

12

GOOS KANT

well as the revised version of it, given by Hsu and Ramachandran w14x.. These algorithms consist of the following three stages: Stage 1 makes G connected, for which we can use CONNECTŽ G . of Section 2. Hence assume that G is connected. Let TB C its BC-tree, and we want to add at most max d y 1, u pr2v4 edges. Stage 2 eliminates the massive nodes from TB C . Let ¨ * be a massive node Žif present.. Let g be the number of components of TB C y  ¨ *4 containing only one leaf. Call such components 1-chains. There are dŽ ¨ *. y g components containing at least two leaves, so it follows that p G g q 2Ž dŽ ¨ *. y g .. We pick ¨ * as the root of TB C and number the leaves of TB C from left to right by ¨ Ž1., . . . , ¨ Ž p .. Eliminating the massive node ¨ * is now done by Stage 2 of the algorithm of w14x: add 2 d edges such that as many 1-chains as possible are coalesced into one. We only add edges between consecutive leaves, which preserves the planarity. Let G9 be the augmented graph by adding the 2 d edges of A between the corresponding pendants. This is done by adding edges between exterior vertices on the last blocks of the corresponding chains. This preserves the planarity in G9. Let TBX C be the BC-tree of G9 with p9 leaves, with p9 s p y 2 d . Let d9Ž ¨ . denote the d-value of ¨ in TBX C . The correctness of Stage 2 follows from the following theorem. LEMMA 5.4 w26x.

For all C-nodes ¨ of TBX C , d9Ž ¨ . y 1 F u pr2v holds.

The remaining part of this section considers Stage 3. Assume for this that the BC-tree TB C of G is balanced and has p leaves. The goal is to add u pr2v edges such that G is biconnected and planar. Stage 3 in the algorithm of Rosenthal and Goldner w26x and Hsu and Ramachandran w14x is based on the following idea: find the C-vertices ¨ and w in TB C with largest degree. Find two leaves y and z such that the path between them passes through ¨ and w. Add an edge between non-cutpoint vertices in the corresponding blocks, represented by y and z in TB C . ŽSome special rules are formulated if there are at most three leaves or if there is only one C-vertex in TB C w14x.. Now the problem arises with respect to planarity: the BC-tree is fixed, hence we cannot guarantee that adding an edge between two leaves y and z Žas explained in the previous paragraph. preserves the planarity. Let us be more precise about this. Number the leaves of TB C ¨ Ž1., . . . , ¨ Ž p . from left to right. Two leaves y and z in TB C are called consecuti¨ e, if they have number ¨ Ž i . and ¨ Ž i q 1., for some i, 1 F i - p. We now look in every step for two consecutive leaves y and z, satisfying the leaf-connecting condition and such that the path P between them in TB C passes through all critical nodes. We will show that these pairs always exist. Moreover we show that this leads to the minimum number of added edges.

AUGMENTING OUTERPLANAR GRAPHS

13

To find nodes of degree ) 2 quickly during the algorithm, we eliminate the nodes of degree 2 of the BC-tree in every step Žexcept the root., by contracting their two incident edges into one. This can be done in O Ž1. time per vertex of degree 2. The algorithm becomes as follows: OUTERBICONNECT Ž G .  G has at least 3 nodes and TB C is balanced;4 Let TB C be rooted at an arbitrary B-node b*; while p G 2 do if d s 2 then let ¨ be a B-node Ždifferent from b*. with degree ) 2 else let ¨ be a C-node with the largest degree in TB C ; use algorithm PATHFINDERŽ ¨ . to find a node w with degree ) 2 and two adjacent leaves y and z such that the path between them passes through ¨ and w; find non-cutvertices a and b in the corresponding blocks of G represented by y and z, respectively; add an edge between a and b and update TB C od; END OUTERBICONNECT v

v

v

v

The important point in this algorithm is the procedure PATHFINDER, that finds a node w and two adjacent leaves y and z whose path P between them passes through ¨ and w. Recall that any order of children of a C-node is allowed, but the children of a B-node may only be swapped from a left-to-right order into a right-to-left order Žor vice versa.. The algorithm becomes as follows, when starting with ¨ . PATHFINDERŽ ¨ . As long as ¨ is not the root of TB C , and ¨ can be made the leftmost child of its parent, say w, make ¨ the leftmost child of w, ¨ [ w. From ¨ follow the leftmost child pointers to a leaf, y. From the brother left to ¨ follow the rightmost child pointers to a leaf, z. END PATHFINDER v

v v

This algorithm differs significantly from the PATHFINDER algorithm, described by Rosenthal and Goldner w26x and Hsu and Ramachandran w14x. In w14, 26x, the constructed path P always contains the root of TB C and the two C-nodes with highest degree. Hence our algorithm is a simplification of their algorithms. We now show that our algorithm satisfies the required condition. To this end, we have to use a different data structure for TB C as in w14, 26x.

14

GOOS KANT

LEMMA 5.5. The algorithm can be implemented to run in linear time. Proof. For TB C we use the datastructure of the PQ-tree, as described by Booth and Lueker w1x: every node in TB C is represented by a record, and all children of a node are stored in a double linked list. Every node, which is not a leaf, has pointers to its leftmost and rightmost child. All children of a C-node and the left- and rightmost child of a B-node have a pointer to its parent. Testing whether a node ¨ can be made the leftmost child of its parent is done by testing whether the parent-pointer of ¨ is not nil. Making ¨ the leftmost child of its parent, say w, is done by changing a few pointers: if w is a B-node, then its leftmost and rightmost pointer can be swapped; if w is a C-node, then ¨ and the leftmost child of w can be swapped. Using the leftmost and rightmost child pointers, the required leaves y and z can be reached. Updating the tree after adding the edge between the blocks of y and z is done as follows. Let P be the path between y and z in TB C . If dŽ b*. G 3, then the least common ancestor of y and z is always a B-node, say b1. Let w 1 , w 2 be two children of b1 , part of P. We walk from y to z and make every C-node a child of b1 and we make all children of a B-node children of b1. We store them between w 1 and w 2 in the order we visit them between y and z. If the least common ancestor of y and z is a C-node c1 , then we take a new B-node b1 , do the same as above, and add finally b1 as child of c1 in the tree TB C . This precisely corresponds with the new block. The total time spent for finding the leaves y and z and updating TB C is O Ž< P <., with < P < the length of the path P between y and z. For the required total time for updating all paths P, we know, by Theorem 5.2, that the number of times a node is visited is no more than its degree. Since the summation of the degrees of all nodes in a tree with n nodes is O Ž n., the total time remains linear. Total time spent finding the highest degree C-nodes is O Ž n., as described by w26x: Initially do a bucket sort to obtain lists list Ž i . of C-nodes which have degree i. It takes constant time to remove a vertex ¨ from a list list Ž i . and place it into list Ž j ., and to determine the vertex with highest degree. If there is no C-vertex in TB C anymore, then we have to take a B-vertex of degree ) 2. Notice that the root b* or one of its children must have degree ) 2, hence we can easily find such a B-node in O Ž1. time. The leaves y and z are obtained by following from two consecutive siblings in a tree the rightmost and leftmost pointers to the leaves. Hence the following lemma is easy to prove.

AUGMENTING OUTERPLANAR GRAPHS

LEMMA 5.6.

15

y and z are consecuti¨ e.

This means that we can add an edge Ž a , b . between two non-cutvertices of the blocks of y and z without destroying the planarity. LEMMA 5.7.

y and z satisfy the leaf-connecting condition.

Proof. Let ¨ be the starting node in PATHFINDER, then dŽ ¨ . ) 2. When we stop in the while-loop of PATHFINDER, then either parent Ž w . s b* or parent Ž w . s nil and, hence, has degree ) 2 and is part of path P. Assume w.l.o.g. that dŽ b*. - 3, thus b* has degree 1, because we eliminated all nodes with degree 2 from TB C . w has degree at least 3 because all nonleaf vertices have degree at least 3. If w / ¨ then we have two nodes with degree ) 2 on the path, so assume w s ¨ . Hence ¨ is the only child of b*. If ¨ is a C-node and there is another node ¨ 9 with degree ) 2 in TB C , then ¨ 9 is the leftmost or rightmost child of ¨ , because the children of each C-node in TB C are sorted such that all nonleaf children occur at one side. But path P is constructed by taking from ¨ the leftmost child pointers and taking from b* the rightmost child pointers. Hence ¨ 9 is part of P. Assume finally that ¨ is a B-node Žhence d s 2.. If ¨ has degree ) 3 then w s ¨ satisfies the leaf-connecting condition, so assume ¨ has only two children. Since ¨ is the only child of b*, both children of ¨ are part of P. Since p ) 3, it follows that at least one of them is not a leaf, i.e., has degree at least 3 and is part of P. Hence leaves y and z always satisfy the leaf-connecting condition. Now we are able to prove the following variant of Claim 1 in w14x. LEMMA 5.8. For outerplanar balanced graphs G the algorithm OUTERBICONNECT finds a set S of u pr2v edges such that, when S is added to G, a biconnected planar graph is obtained. Proof. Assume w.l.o.g. that p ) 3. In this case, a critical node must have degree more than 2. Case 1: TB C has two critical nodes ¨ and w. All other nonleaf vertices have degree 2 and, hence, are eliminated from the tree. Since PATHFINDER will find another node with degree ) 2 if present, both ¨ and w will be part of P. Case 2: TB C has only one critical node ¨ . OUTERBICONNECT takes the C-node with highest degree, thus ¨ is part of P. Since TB C is balanced and p ) 3, there exists a node w / ¨ with degree more than 2, otherwise ¨ is massive. PATHFINDER find a node w with degree ) 2 by Lemma 5.7. Case 3: TB C has no critical node. OUTERBICONNECT will take the C-node with highest degree if d G 2, otherwise it takes a B-node with degree G 3. In both cases PATHFINDER finds a node w / ¨ with degree ) 2 on path P.

16

GOOS KANT

In all three cases, we find two nodes of degree more than 2 or a B-node of degree more than 3. Thus by Lemma 5.2, the number of leaves in the new BC-tree reduces by two. When ¨ or w is critical, the value of d reduces by 1. Thus the BC-tree remains balanced. Hence the lower bound of Theorem 5.3 is achieved by the algorithm. These lemmas lead to the following result. THEOREM 5.9. There is a linear time and space algorithm to augment outerplanar graphs by adding a minimum number of edges such that the resulting graph is biconnected and planar. 6. TRICONNECTIVITY 6.1. Triconnecting Biconnected Outerplanar Graphs We now consider the problem of how to augment an outerplanar graph G by adding a minimum number of edges such that the augmented graph G9 is triconnected and planar. To this end we first restrict our attention to biconnected outerplanar graphs, which are cycles with non-intersecting chords. Every vertex with degree 2 must get an additional edge. Every biconnected outerplanar graph has at least two vertices ¨ , with deg Ž ¨ . s 2 w23x. Let K be the number of vertices of degree 2, then we will show that the number of edges to be added to achieve triconnectivity is equal to u Kr2v, which is optimal. It is not very difficult to construct an example where the outerplanar embedding Žall vertices occuring on the outerface. has to be changed to obtain an optimal augmentation. As an example, consider the cycle on vertices ¨ 1 , . . . , ¨ k and let k vertices w 1 , . . . , w k be given with wi connected to ¨ i and ¨ iq1 Ž1 F i - k .. Vertex w k is connected to ¨ 1 and ¨ k . The resulting graph G is outerplanar and each vertex wi must receive an augmenting edge Žsee Fig. 6a.. Hence at least u kr2v edges must be added. Suppose we want to augment this graph with u kr2v edges. Assume edge Ž wi , wj . is added, with j ) i and j y i as small as possible. If j s i q 1 then it follows that G y  ¨ i , ¨ iq2 4 is disconnected. If j ) i q 1 then we cannot add an edge from wiq1 without crossing edge Ž wi , wj .. Hence we cannot augment the graph by u kr2v edges to a triconnected graph without changing the embedding. When we change the embedding, then it is possible, as shown in Fig. 6b. Let G be an outerplanar graph with a given outerplanar embedding. Assume the vertices are numbered ¨ 1 , . . . , ¨ n along the outerface. We now construct the dual graph G* of G: every interior face F of G is represented by a vertex wF in G*. There is an edge between two vertices Ž wF , wF 9 . in G*, iff F and F9 share an edge in G. We also represent every vertex ¨ of degree 2 by a vertex ¨ in G*, and add the edge Ž ¨ , ¨ F ., iff

AUGMENTING OUTERPLANAR GRAPHS

17

FIG. 6. Triconnecting a biconnected outerplanar graph. Ža. The initial graph G. Žb. The triconnected augmentation.

¨ g F in G. Observe that G* is a tree and the leaves of G* are the

vertices of degree 2 in G. Notice also that if ¨ i and ¨ j share an interior face and j y i ) 1, then G y  ¨ i , ¨ j 4 is disconnected. If j y i ) 1, then there is a vertex ¨ k with deg Ž ¨ k . s 2 and i - k - j. Assume ¨ i and ¨ j share face F then vertex wF has descendant leaf ¨ k . If we add edges to G* such that there is a path P from ¨ k to a vertex ¨ l , not a descendant of wF and wF f P, then it follows that ¨ i and ¨ j are not a cutting pair anymore. This observation leads to the following lemma: LEMMA 6.1. If G* is balanced, then applying OUTERBICONNECT to G*, and adding the corresponding edges in G gi¨ es a triconnected graph. Proof. Let G9 be the augmented graph of G after applying OUTERBICONNECT to G*. Consider two vertices ¨ i and ¨ j . G y  ¨ i , ¨ j 4 split the outerface of G into two paths: a path P1 from ¨ iq1 to ¨ jy1 , and a path P2 from ¨ jq1 to ¨ iy1. If ¨ i and ¨ j do not share an interior face, then there is chord Ž ¨ k , ¨ l . in between, connecting P1 with P2 . Hence G y  ¨ i , ¨ j 4 is connected. Assume further that ¨ i and ¨ j share an interior face F and let j ) i q 1. It is easy to prove that there exists a vertex ¨ k of degree 2 and i - k - j. If we delete wF in the augmentation G9* of G*, then the graph G9* is still connected. Let Ž ¨ a , ¨ b . be an added edge in G9*, with ¨ a a descendant of wF and ¨ b not a descendant of wF in G*. This implies that i - a - j and b - i or b ) j. There is an edge between P1 and P2 in G9, hence ¨ i and ¨ j are not a cutting pair in G9. Since this holds for every pair ¨ i , ¨ j Ž j ) i ., this proves the lemma. In the algorithm OUTERBICONNECT the order of the children of a C-node is changed from time to time, to preserve the planarity. How can we deal with this problem here, since the embedding of G* Žhence the

18

GOOS KANT

order of the children. is fixed. The solution we present here is as follows: We root G* at an arbitrary vertex of degree at least 2, say br . We assume that every leaf is a B-node, and every nonleaf node is a C-node, but with fixed ordering of the children. After finding ¨ with maximal dŽ ¨ ., we walk toward br , until the current node is not the leftmost child of its parent, or the parent is br . Let w be the parent. If w / br , then w had degree at least 3, which is sufficient to satisfy the leaf-connecting condition. Hence Lemma 5.2 still holds. Of course, planarity is preserved. The only point is now when the graph is not balanced, or in other words: how to implement Stage 2? Recall that a 1-chain is a component of TB C y  ¨ 4 , containing only one leaf. The solution we present is to add edges between the 1-chains inside the shared interior face. More precisely, let ¨ * be the massive node in G*, i.e., dŽ ¨ *. ) u pr2v y 1. Root G* at ¨ * and let ¨ Ž1., . . . , ¨ Žg . be the leaves from left to right in G*, which are 1-chains. We now add an edge between 1-chain ¨ Žu gr2v y i . and ¨ Žu gr2v q i ., for 1 F i - d with d s dŽ ¨ *. y 1 y u pr2v. Adding the edges in a similar way to G preserves the planarity. Since p G 2 dŽ ¨ *. y g Žsee Section 5. it follows that d F u gr2v y 1. Let G9 be the augmented graph and let GU1 be the resulting tree with p9 leaves, with p9 s p y 2 d . Let d9Ž ¨ . denote the d-value of ¨ in GU1 . The following variant of Lemma 5.4 can be proved. LEMMA 6.2.

For all nodes ¨ of GU1 , d9Ž ¨ . y 1 F u p9r2v holds.

Proof. For ¨ * holds that d9Ž ¨ *. y 1 s dŽ ¨ *. y 1 y 2 d s u pr2v y d s u p9r2v. Consider a ¨ / ¨ *, and suppose that d9Ž ¨ . y 1 ) u p9r2v. Now p G dŽ ¨ *. q dŽ ¨ . y 2 s Ž dŽ ¨ *. y 1. q Ž dŽ ¨ . y 1. ) Žu pr2v q d . q u p9r2v s Žu pr2v s Žu pr2v q d . q Žu pr2v y d . s 2u pr2v G p, which is a contradiction. After this we apply the algorithm OUTERBICONNECT on the graph G9* as described above. The corresponding edges are added in the outerface of G. Since this algorithm works in linear time and space, we obtain the following result. LEMMA 6.3. There exists a linear time algorithm to augment a biconnected outerplanar graph G by adding a minimum number of edges such that the augmented graph G9 is triconnected and planar. See Fig. 7 for an example. 6.2. Triconnecting Outerplanar Graphs To triconnect outerplanar graphs G, which are nonbiconnected, we use the technique of the previous section. Assume G is connected, otherwise the algorithm of Eswaran and Tarjan w6x is applied. We now recognize the blocks of G and build the BC-tree TB C . Notice that if a block Bi contains two cutvertices, c1 and c 2 , then deleting c1 and

AUGMENTING OUTERPLANAR GRAPHS

19

c 2 disconnects G. To be more precise about the blocks, which must receive an augmenting edge, we state the following lemma, which can be verified quite easily. LEMMA 6.4. A block Bi in an outerplanar graph needs at least one augmenting edge in any triconnecti¨ ity augmentation if and only if there is a ¨ ertex of degree 2 in Bi or its corresponding B-node has degree 2 in TB C . Let one arbitrary B-node b* be the root of TB C . Again the order of the children of a B-node is fixed. We assume that the left-to-right order of the children of a B-node corresponds to walking counterclockwise around the outerface of the corresponding block. The idea is to apply OUTERBICONNECT bottom-up to the corresponding blocks of TB C . When visiting pendant block Bi , we add all but one

FIG. 7. Triconnecting a biconnected outerplanar graph. Ža. The initial graph G. Žb. The tree G*. Žc. Applying OUTERBICONNECT to G*. Žd. The optimal triconnectivity augmentation.

20

GOOS KANT

augmenting edge to Bi , i.e., two or three vertices with degree 2 remain in the augmentation of Bi , denoted by BiX . Let Bj be the incident block of Bi in G. We represent BiX by a vertex ¨ BXi with k leaves as children in the dual graph BUj of Bj . k is the number of vertices of degree 2 in BiX . Applying OUTERBICONNECT to Bj implies that at least k q 1 vertices of Bi have edges to vertices outside Bi , namely, the k vertices of degree 2 in BiX and the unique cutvertex of Bi . This leads to the following lemma. LEMMA 6.5. After applying OUTERBICONNECT to BUj and deleting any 2 ¨ ertices in the augmentation of Bi , Bi is still connected to Bj . Proof. Assume k s 2 Žthe proof is similar for k s 3.. Let ¨b and ¨g be the vertices of degree 2 in BiX . Let Bi j Bj s ¨a . ¨b and ¨g receive an edge to Bj , i.e., there is a path between ¨b and ¨g outside Bi . In Section 6.1, an edge Ž ¨b , ¨g . was added, i.e., also a path between ¨b and ¨g . Hence we can apply Lemma 6.1: after deleting any two vertices of Bi , all the other vertices of Bi can still reach ¨a , ¨b or ¨g , which are connected to Bj . Using this lemma, the algorithm can now be described as follows. OUTERBICONNECT Ž G . Let TB C be rooted at an arbitrary B-node br . Number the B-nodes of TB C in postorder, say b1 , . . . , bk , bk s br . for i [ 1 to k do Compute the dual graph G*i of Bi ; Let c1 , . . . , c l be the cutvertices of Bi , with c l s parent Ž bi ., if bi / b* Ži.e., i - k .; for l [ 1 to j y 1 do Represent each component of G y  c l 4 Žexcept the one, containing Bi . as a vertex, neighbored to c l in G*i , with k children, k the number of vertices of degree 2 in the current augmentation of this component. rof Apply OUTERBICONNECT to G*i , and add all but the last edge to G, if i - k. rof END OUTERTRICONNECT The implementation can be made such that the time in each step is O Ž< Bi <., where < Bi < is the number of vertices of the block, we are currently visiting. Combining this with Lemma 6.5 gives the following result. THEOREM 6.6. There is a linear time and space algorithm to augment on outerplanar graph G by a minimum number of edges such that the resulted graph is triconnected and planar.

AUGMENTING OUTERPLANAR GRAPHS

21

7. TRIANGULATING OUTERPLANAR GRAPHS 7.1. Triangulating One Interior Face Let G be an embedded outerplanar graph, and the problem is to triangulate one interior face of it, while minimizing the maximum degree. ŽThis algorithm can be used to triangulate any face in an embedded planar graph as well.. The core technique of this algorithm is dynamic programming. Dynamic programming has been applied to several related triangulation algorithms of polygons, described by Edelsbrunner and co-workers w3]5x. They present polynomial time algorithms for triangulating polygons while maximizing the minimum height, minimizing the maximum slope, or minimizing the maximum eccentricity. Unfortunately, these algorithms cannot be translated to our problem. Let G be an embedded outerplanar graph. Let F be an interior face on k vertices, numbered ¨ 1 , . . . , ¨ k clockwise around the face. Every vertex ¨ i of F has degree G 2. Some edges Ž ¨ i , ¨ j ., j ) i q 1 may occur outside F, which we will call forbidden edges. Notice that in any triangulation of F the vertices ¨ 1 and ¨ k have a common neighbor ¨ p Ž2 F p F k y 1. inside face F. The edges Ž ¨ 1 , ¨ p . and Ž ¨ k , ¨ p . splits the face F into three faces: F1 with vertices ¨ 1 , . . . , ¨ p , F2 with vertices ¨ p , . . . , ¨ k , and the triangle F3 on ¨ 1 , ¨ p and ¨ k . The idea is to inspect all possibilities of ¨ p and to recursively triangulate F1 and F2 , while minimizing the maximum degree. See Fig. 8. Let for this approach incrF Ž ¨ i . be the increase of deg Ž ¨ i ., while triangularing F. To deal with the case p s 2 or p s k y 1 Žthen the edge Ž ¨ 1 , ¨ 2 . or Ž ¨ ky 1 , ¨ k . is already present. we delete the edges Ž ¨ i , ¨ iq1 . Ž1 F i - k . initially from G. We decrease deg Ž ¨ i . by 2. Let Fi j denote the face on vertices ¨ i , . . . , ¨ j . Let Dw i, j, i9, j9x denote the maximum degree of Fi j by a triangulation with incrF i jŽ ¨ i . s i9 and incrF i jŽ ¨ j . s j9. If such a triangulation

FIG. 8. Recursive definition of the triangulation of one face.

22

GOOS KANT

does not exist, Dw i, j, i9, j9x s `. A simple analysis shows the following recursive formula if i - j y 1: D w i , j, i9, j9 x [

min i-p-j 0Fp9, p0 Fjy1 Ž i , p . and Ž j, p . not forbidden

 max  D w i , p, i9 y 1, p9 x , D w p, j, p0 , j9 y 1x , deg Ž ¨ i . q i9 q 1, deg Ž ¨ j . q j9 q 1, deg Ž ¨ p . q p9 q p0 q 2

4 4 If j s i q 1 then for all i9, j9 G 0: Dw i, j, i9, j9 s max deg Ž ¨ i ., deg Ž ¨ j .4 . We want to compute min i9, j9 Dw1, k, i9, j9x, deg Ž ¨ 1 . q i9 q 1, deg Ž ¨ k . q j9 q 14 . Using dynamic programming, based on the above formulas, and some other ideas which help to decrease the running time of the algorithm, the following theorem follows. THEOREM 7.1. There is an exact O Ž k 3 d log d . time algorithm to triangulate one face of k ¨ ertices of a graph G with maximum degree d such that the maximum degree of the triangulation is minimized. Proof. Let G be an embedded outerplanar graph, and let F be an interior face on k vertices. Let d be the maximum degree of G. It is shown in w16x and G can be triangulated such that the maximum degree of the triangulation is at most uŽ3r2. d v q O Ž1.. We do not compute all values of Dw i, j, i9, j9x as this would be too time-consuming, but instead apply binary search on the maximum degree. So we test for O Žlog d . values of K whether a triangulation with maximum degree F K exists. Let DK w i, j, i9, j9x s true m Dw i, j, i9, j9x F K. Suppose K is fixed. Note that it is sufficient to know: for all i9, 1 F i9 F K y deg Ž ¨ i ., the smallest value of j9 such that DK w i, j, i9, j9x s true and for all j9, 1 F j9 F K y deg Ž ¨ j ., the smallest value of i9 such that DK w i, j, i9, j9x s true. Denote these smallest values with FK w i, j, i9x and GK w i, j, j9x. ŽIf such j9 or i9 not exist, FK w i, j, i9x s `, or GK w i, j, j9x s `.. Now DK w i, j, i9, j9x s true, if and only if there exists a p, i - p - j, Ž ¨ i , ¨ p . and Ž ¨ j , ¨ p . not forbidden and FK w p, j, K y deg Ž ¨ p . y FK w i, p, i9x y 2x F j9. ŽThe increase of the degree of ¨ p in face Fp j may not be larger than K y deg Ž ¨ p . y FK w i, p, i9x y 2. FK w i, p, i9x edges are used for face Fi p , and there are edges Ž i, p ., Ž p, j ... So FK w i, j, i9x s min FK w p, j, K y deg Ž ¨ p . y F w i, p, i9x y 2x N i - p - j, Ž i, p ., Ž p, j . not forbidden4 . The latter formula allows us to compute all values of FK w i, j, i9x Ž1 F i F k, 0 F i F p . in O Ž k 3 K . time. When FK is computed, one easily determines whether a triangulation with maximum degree F K exists. Using binary

AUGMENTING OUTERPLANAR GRAPHS

23

search on K, we can implement it such that the total runtume becomes O Ž k 3d log d .. 7.2. Triangulating All Interior Faces Let G be an embedded connected outerplanar graph. Assume first G contains a bridge, say Ž u, ¨ . between subgraphs B1 and B2 . Given a maximum degree K for B1 , no information of the added edges is used for the triangulation of B2 . Hence we can apply the traingulation algorithm Žfor certain upper bound K . to all bridge-connected components in parallel. Let G be bridge-connected. We construct the following tree T : every interior face F of G is a node ¨ F in T, and there are two types of edges Ž ¨ F , ¨ F ., which are added to T : a b Fa and Fb share an edge Žhence Fa and Fb belong to the same block., or v

v

Fa and Fb belong to different blocks, but share a cutvertex in G.

T is rooted at an arbitrary node ¨ F . If ¨ Fa is the parent of ¨ F b in T, then Fa is called the parent-face of Fb . Let T¨ F be the subtree of T, rooted at ¨ F , and let GŽ ¨ F . be the corresponding subgraph. Let ¨ Fa parent of ¨ F b in T. If Fa and Fb share Ž ¨ i , ¨ j ., then we define Dw ¨ i , ¨ j , i9, j9x to be the maximum degree of the triangulation of G¨ F , such b that the degree increase of ¨ i and ¨ j is at most i9 and j9, respectively. If Fa and Fb share cutvertex ¨ i , then we define Dw ¨ i , i9x to be the maximum degree of the triangulation of G¨ F , such that the degree increase of ¨ i is b at most i9. We now use a procedure, similar to the one, described in Section 7.1. Apply binary search on the maximum degree K. For a fixed K, define FK w i, j, i9x and GK w i, j, j9x as in the proof of Theorem 7.1. Define HK Ž i . s min i9 N Dw i, i9x F K 4 . Compute the tables or values for FK , GK and HK bottom up in the tree H. When we deal with a face, we add HK Ž i . to the degree of ¨ i . Let the tables FK w i, j, i9x and GK w i, j, j9x play the same role as they played in the proof of Theorem 7.1. With minor modifications of this algorithm, one can compute the table FK w ¨ Xi , ¨ Xj , i9x and GK w ¨ iX , ¨ Xj , j9x for the edge Ž ¨ Xi , ¨ Xj . of Fb , or compute the contribution to HK w ¨ Xi x for the cutvertex X ¨ i of Fb . We omit some easy details here. Applying a similar proof as in Theorem 7.1, the following result can be obtained. THEOREM 7.2. There is an O Ž n3d log d . algorithm to triangulate all interior faces of an outerplanar graph G with maximum degree d, while minimizing the maximum degree.

24

GOOS KANT

REFERENCES 1. K. S. Booth and G. S. Lueker, Testing for the consecutive ones property, interval graphs and graph planarity testing using PQ-tree algorithms, J. Comput. System Sci. 13 Ž1976., 335]379. 2. G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis, Algorithms for automatic graph drawing: An annotated bibliography, Comp. Geometry Theory Appl. 4 Ž1994., 235]282. 3. H. Edelsbrunner, ‘‘Triangulations,’’ Tech. Report CS 497, Dept. of Comp. Science, Univ. of Illinois at Urbana]Champaign, 1991. 4. H. Edelsbrunner and T. S. Tan, A quadratic time algorithm for the minmax length triangulation, in ‘‘Proc. 32nd Annual IEEE Symp. on Found. of Comp. Science, 1991,’’ pp. 548]559. 5. H. Edelsbrunner, T. S. Tan, and R. Waupopitsch, An O Ž n2 log n. time algorithm for the minmax angle triangulation, in ‘‘Proc. 6th Annual ACM Symp. on Computational Geometry, 1990,’’ pp. 44]52. 6. K. P. Eswaran and R. E. Tarjan, Augmentation problems, SIAM J. Comput. 5 Ž1976., 653]665. 7. G. N. Frederickson and J. Ja’Ja, Approximation algorithms for several graph augmentation problems, SIAM J. Comput. 10 Ž1981., 270]283. 8. A. Frank, Augmenting graphs to meet edge-connectivity requirements, in Proc. 31st Annual IEEE Symp. on Found. on Comp. Science, 1990,’’ pp. 708]718. 9. H. N. Gabow, Applications of a poset representation to edge connectivity and graph rigidity, in ‘‘Proc. 32nd Annual IEEE Symp. on Found. of Comp. Science, 1991,’’ pp. 812]821. 10. A. Garg and R. Tamassia, Planar drawings and angular resolution: Algorithms and bounds, in ‘‘Proc. 2nd European Symposium on Algorithms ŽESA ’94., 1994,’’ pp. 12]23. 11. F. Harary, ‘‘Graph Theory,’’ Addison]Wesley, Reading, MA, 1969. 12. T.-S. Hsu, On four-connecting a triconnected graph, in ‘‘Proc. 33rd Annual IEEE Symp. on Found. of Comp. Science, 1992,’’ pp. 70]79. 13. T.-S. Hsu and V. Ramachandran, A linear time algorithm for triconnectivity augmentation, in ‘‘Proc. 32nd Annual IEEE Symp. on Found. of Comp. Science, 1991,’’ pp. 548]559. 14. T.-S. Hsu and V. Ramachandran, On finding a smallest augmentation to biconnect a graph, in ‘‘Proc. 2nd Annual Int. Symp. on Algorithms,’’ Lecture Notes in Computer Science, Vol. 557, pp. 326]335, Springer-Verlag, BerlinrNew York, 1992. 15. Deleted in proof. 16. G. Kant, ‘‘Algorithms for Drawing Planar Graphs,’’ Ph.D. thesis, Dept. of Computer Science, Utrecht University, 1993. 17. Deleted in proof. 18. G. Kant and H. L. Bodlaender, Triangulating planar graphs while minimizing the maximum degree, in ‘‘Proc. 3rd Scand. Workshop on Algorithm Theory,’’ Lecture Notes in Comp. Science, Vol. 621, pp. 258]271, Springer-Verlag, BerlinrNew York, 1992. 19. Deleted in proof. 20. Y.-L. Lin and S. S. Skiena, ‘‘Complexity Aspects of Visibility Graphs,’’ Report 92-08, Dept. of Comp. Science, State Univ. of New York, Stony Brook, 1992. 21. S. Malitz and A. Papakostas, On the angular resolution of planar graphs, in ‘‘Proc. 24th Annual ACM Symp. Theory of Computing, 1992,’’ pp. 527]538. 22. J. Manning and M. J. Atallah, ‘‘Fast Detection and Display of Symmetry in Outerplanar Graphs,’’ Technical Report CSD-TR-606, Dept. of Computer Sciences, Purdue Univ., West Lafayette, IN, 1986.

AUGMENTING OUTERPLANAR GRAPHS

25

23. S. L. Mitchell, Linear algorithms to recognize outerplanar and maximal outerplanar graphs, Inform. Process. Lett. 9 Ž1979., 229]232. 24. D. Naor, D. Gusfield, and C. Martel, A fast algorithm for optimally increasing the edge-connectivity, in ‘‘Proc. 31st Annual IEEE Symp. on Found. of Comp. Science, 1990,’’ pp. 698]707. 25. R. C. Read, A new method for drawing a graph given the cyclic order of the edges at each vertex, Congr. Numer. 56 Ž1987., 31]44. 26. A. Rosenthal and A. Goldner, Smallest augmentations to biconnect a graph, SIAM J. Comput. 6 Ž1977., 55]66. 27. R. E. Tarjan, A note on finding the bridges of a graph, Inform. Process. Lett. 2 Ž1974., 160]161. 28. W. T. Tutte, Convex representations of graphs, Proc. London Math. Soc. 10 Ž1960., 304]320. 29. T. Watanabe, Y. Higashi, and A. Nakamura, Graph augmentation problems for a specified set of vertices, in ‘‘Proc. 1st Annual Int. Symp. on Algorithms,’’ Lecture Notes in Comp. Science, Vol. 450, pp. 378]387, Springer-Verlag, BerlinrNew York, 1990. 30. T. Watanabe and A. Nakamura, Edge-connectivity augmentation problems, J. Comput. System Sci. 35 Ž1987., 96]144. 31. T. Watanabe and A. Nakamura, 3-connectivity augmentation problems, in ‘‘Proc. 1988 IEEE Int. Symp. on Circuits and Systems,’’ pp. 1847]1850. 32. T. Watanabe, M. Yamakado, and K. Onaga, A linear time augmenting algorithm for 3-edge-connectivity augmentation problems, in ‘‘Proc. 1991 IEEE Int. Symp. on Circuits and Systems,’’ pp. 1168]1171.