A linear algorithm to recognize maximal generalized outerplanar graphs

Mathematica Bohemica José Cáceres; Alberto Márquez A linear algorithm to recognize maximal generalized outerplanar graphs Mathematica Bohemica, Vol. 122 (1997), No. 3, 225–230 Persistent URL: http://dml.cz/dmlcz/126148 Terms of use: © Institute of Mathematics AS CR, 1997 Institute of Mathematics of the Czech Academy of Sciences provides access to digitized documents strictly for personal use. Each copy of any part of this document must contain these Terms of use. This document has been digitized, optimized for electronic delivery and stamped with digital signature within the project DML-CZ: The Czech Digital Mathematics Library http://dml.cz 122(1997) MATHEMATICA BOHEMICA No. 3, 225-230 A LINEAR ALGORITHM TO RECOGNIZE MAXIMAL GENERALIZED OUTERPLANAR GRAPHS JOSE CACERES, Almeria, ALBERTO MARQUEZ, Sevilla (Received November 16, 1994, revised May 16, 1996) Summary. In this work, we get a combinatorial characterization for maximal generalized outerplanar graphs (mgo graphs). This result yields a recursive algorithm testing whether a graph is a mgo graph or not. Keywords: outerplanar graph, generalized outerplanar graph MSC 1991: 05C10, 05C75 1. INTRODUCTION The main concept of this paper was introduced by Sedlacek in [6]. He defined generalized outerplanar graphs as graphs with a planar representation such that, at least, one end-vertex of each edge lies on the outer face. Also, he gave a characterization in terms of forbidden subgraphs (see Figure 1). Clearly, this is a way to generalize the well-known concept of outerplanar graph. These two kinds of graphs have been used in the design of printed boards where it is required that all terminals (or one end-terminal of each wire) be placed on the periphery of the chip of the board [3]. Of course, it would be very useful to get linear algorithms for recognizing outerplanar and generalized outerplanar graphs. The former was obtained by Mitchell in [4], and, in this paper, we present a linear algorithm for the recognition of maximal generalized outerplanar graphs since a test whether a graph is generalized outerplanar or not, easily follows from our algorithm. A maximal generalized outerplanar (mgo) .graph is a generalized outerplanar graph such that no edge can be added without violating this property. 225 Figure 1. The forbidden subgraphs of Sedlacek We will use [1] for the common graph notation, except for using the terms vertex instead of point, and edge instead of line. Nonetheless, let us recall some helpful concepts. A graph G is 2-connected when at least two vertices of G must be removed to disconnected it; if there are two vertices, u and v, of G such that their removal disconnects G, we call them a separation pair. The graph induced by u, v and the vertices of the connected component of G - {u,v} is called a split graph. A 2-connected graph with no separation pair is said to be 3-connected and a maximal 3-connected subgraph is called a 3-component. Also, we mention a special kind of graphs. For n > 4, the wheel W„ is defined to be the graph K\ + Cn-\. In [7], Tutte showed that every 3-connected graph either is a wheel or can be built by a sequence of the following two operations over Wn: 1. Add a new edge. 2. Replace a vertex w having a degree at least 4 by two adjacent vertices w' and w" such that each vertex formerly joined to w is joined to exactly one of w' and w" so that in the resulting graph, w' and w" have a degree at least 3. 2. THE RESULTS The previous result yields Lemma 1. A 3-connected maximal generalized outerplanar graph is a wheel. 226 Proof. If we try to construct a mgo 3-connected graph from a wheel by applying the two Tutte's operations then we realize that we are just allowed to add an edge between two non-consecutive vertices of the periphery of the wheel but this new graph is not generalized outerplanar because it contains a subgraph homeomorphic to the forbidden subgraph Gi0 (see Figure 1). On the other hand, the only vertex with a degree at least 4 is the center of the wheel, so we can apply operation 2 just to this vertex. But, again, we obtain a nonplanar graph or a graph which contains a subgraph homeomorphic to the Sedlacek subgraph Gn (see Figure 1). D After we have characterized 3-connected mgo graphs, it is straightforward to check the characterization in the 2-connected case. Lemma 2. The only 2-connected maximal generalized outerplanar graph without 3-components is K3. Proof. There exists only one 2-connected graph with 3 vertices: K3, it has no 3-components and it is mgo. So, consider a graph G with at least four vertices. In an outerplane embedding of G, if all vertices lie in the exterior face then the graph is outerplanar, and it is easy to check that an outerplanar graph with at least four vertices cannot be mgo. Thus, there exists a vertex which does not lie in the exterior face but this vertex must be joined only with the vertices vi,...vn of the exterior cycle (every edge has an end-vertex on the exterior face). Without loss of generality, we can suppose that the vertices v%,.. .«„ are consecutive in the cycle. Now, if the edge t>iun exists, then the graph has a 3-component and if the edge vivn does not exist, then G is not maximal because G + v%vn is generalized outerplanar. So, there are no graphs with at least four vertices under the conditions of the lemma, and we have the proof. D Now we are ready to solve the general case. Theorem 3. Let {u, v} be a separation pair of a 2-connected graph G that splits the graph in Gj, ... ,GP. G is a mgo graph if and only if the following four conditions are satisfied: 1. uv is an edge of G\, ... ,GP. 2. Gi, ... ,GP are mgo graphs. 3. At most two of the components Gi, ... ,GP are not isomorphic to K3. 4. JEacJi Gi, ... ,GP has a generalized outerplane embedding such that the edge uv belongs to the exterior face. 227 Proof. Assume that G is a 2-connected graph and {u, v} is a separation pair. Let Z be the exterior cycle of a generalized outerplane embedding of G. Since this cycle connects the graph, the vertices u and v belong to Z. liu and v are consecutive in Z then the edge uv exists, otherwise, since the endvertices of every edge are in the same split graph, the maximality of G implies that the edge uv belongs to G and so, it belongs to Gi,..., Gp (condition 1). Condition 2 follows from the fact that Gj,..., Gp inherit the mgo property of G. By virtue of Lemma 2, all but at most two of the components G\, • • • ,GP are isomorphic to K3. On the other hand, if Gi, G2 and G3 are different from K3 then G3 must be embedded in an internal face of either G\ or G2 and so, G would not be generalized outerplanar (condition 3). Clearly, u and v lie on the exterior face of the embedding of G; (1 ^ i < p) induced by the generalized outerplane embedding of G. If u and v are not consecutive in the exterior cycle then we can split G; into a new 2-connected component and a K3. Thus, uv belongs to the exterior cycle and condition 4 holds. Conversely, we build the generalized outerplane embedding of G in the following way. Consider two components, G' and G", such that they are not simultaneously K3 (see condition 3), and its generalized outerplane embedding such that uv belongs to the exterior cycle (see condition 4). Merging their planar representations, we obtain a generalized outerplane embedding of G' U G" and also, if G' and G" are maximal then this new graph is maximal as well. Now, we can join components isomorphic to K3 losing neither the maximality property nor the generalized outerplanarity property. • 3. THE LINEAR ALGORITHM Theorem 3 is the result we need to design a recursive algorithm for testing whether a graph is mgo or not. Roughly speaking, the algorithm works in the following way: it splits the input graph into two 2-connected components, checks conditions 1 and 3 of Theorem 3 and recursively uses these components as input. During the backtrack of the algorithm, condition 4 is tested and the recursion ends when the situation of Lemma 1 or Lemma 2 occurs. One important step of the algorithm is to find the 3-component of the input graph. The linear algorithm of Hopcroft and Tarjan (see [2]) can be used to do this. Also, in [5], the authors choose to explore the graph by using depth-first search (DFS) and this is the method that our algorithm uses. 228 MGO-TEST Algorithm. Let G be a 2-connected graph with M vertices having a list of vertices V and edges E. Let us suppose that all vertices are labelled with 'interior'. Step 1: If [£"| > 3M - 6 then G is not mgo and stop. If G = K3 then G is mgo and stop. Otherwise: Step 2: Using DFS, check whether G is 3-connected. 1. G is 3-connected. Check whether G is a wheel (the degree of M - 1 vertices is 3). If it is not then G is not mgo and stop. Else: (a) G = K4. G is mgo if and only if there exists a vertex labelled 'interior'. Stop. (b) G 7^ K4. G is mgo if and only if the vertex with a greater degree is labelled 'interior'. Stop. 2. G is not 3-connected. Look for a separation pair {u,v} of G. If uv tfE then G is not mgo and stop. Else, build split graphs G\,...,Gv labelling u and v as 'exterior' in each G;. Except one or two, all the graphs Gi,...,Gp must be K3, or G is not mgo and stop. If G' and G" are such graphs then G is mgo if and only if both G' and G" are mgo. Step 1 ensures that we are not in a trivial case. In 2.2, we define a recursion loop that splits the input graph, checks whether there are the correct number of K3 and deletes them. The condition for ending this recursion is in 2.1 where the algorithm checks whether we have a wheel and whether its center can be placed not in the exterior face. Theorem 4. To test whether a graph is mgo or not, needs time 0(n) with the MGO-TEST algorithm, and this is optimal. Proof. Clearly, the step that dominates the calculation is to check by DFS whether the graph is 3-connected. The cost of this test is 0(n), which completes the proof. • References [1] F. Hаrаry: Graph Theory. Addison Wesley, Reading Mass., 1969. [2] J. E. Hopcroft аnd R. E. Tаrjаn: Dividing a graph into triconnected components. SIAM J. Comput. 2 (1973), 135-158. [3] M. C. vаn Lier аnd R. H. J. M. Otten: C.A.D. of masks and wiring. T. H. Rept. 74-E-44, Dept. Elect. Engrg. Eindhoven University of Technology. [4] 5. Mitchell: Linear algorithms to recognize outerplanar and maximal outerplanar graphs. Inform. Process. Lett. 9 (1979), 229-232. [5] T. Nishizeki, N. Chibа: Planar Graphs: Theory and Algoгithms. North-Holland, Amsterdam, 1969. 229 [6] J.Sedláček: On a generalization of outerplanar graphs. Ćasopis Pěst. Mat. 113 (1988) 213-218. [7] W. T. Tutte: A theory of 3-connected graphs. Indag. Math. 23 (1961), 441-455. Authors' addresses: José Cáceres, Geometría y Topología, Universidad de Almería, 04120 Almería, Spain, e-mail: jcaceresSualm.es; Alberto Márąuez, Matemática Aplicada. I, Universidad de Sevilla, 41012 Sevilla, Spain, e-mail: almarвobelix. cica. es. 330