Consequences of some outerplanarity extensions

ROCKY MOUNTAIN JOURNAL OF MATHEMATICS Volume 42, Number 4, 2012 SURVEY ARTICLE: CONSEQUENCES OF SOME OUTERPLANARITY EXTENSIONS L. BOZA, E.M. FEDRIANI AND J. N´ U˜ NEZ ABSTRACT. In this expository paper we revise some extensions of Kuratowski planarity criterion, providing a link between the embeddings of infinite graphs without accumulation points and the embeddings of finite graphs with some distinguished vertices in only one face. This link is valid for any surface and for some pseudosurfaces. On the one hand, we present some key ideas that are not easily accessible. On the other hand, we state the relevance of infinite, locally finite graphs in practice and suggest some ideas for future research. 1. Introduction. The problem of extending Kuratowski’s planarity criterion [27] to other surfaces different from the sphere, S2,looks very difficult. This statement is shown by the fact that there has been little progress on this research from 1930 until 1979, when Archdeacon [1] and Glover, Huneke and Wang [23] determined the class of finite graphs which cannot be drawn in the projective plane, P2, and which are minimal with this property under topological containment. These graphs were denoted by T(P2), and they found that T(P2) had 103 elements, in front of the only two in T(S2). However, the problem still remains open when dealing with any other compact surface different from S2and P2. More or less at the same time, infinite graphs constituted a relevant generalization of classic, finite graphs. The handling of these graphs presents substantial differences, but it is also possible to find common aspects. In fact, in this paper we establish a link between infinite graphs and finite graphs which verify some properties. Besides, we revise some characterizations of embeddings of infinite graphs, paying 2010 AMS Mathematics subject classification. Primary 05C10 (planar graphs), 05C83 (graph minors), 05C63 (infinite graphs). Keywords and phrases. Graph embeddings, infinite graphs, tubular surfaces, Halin’s theorem, increasing systems. The third author is the corresponding author. Received by the editors on April 25, 2012. DOI:10.1216/RMJ-2012-42-4-1073 Copyright c 2012 Rocky Mountain Mathematics Consortium 1073 1074 L. BOZA, E.M. FEDRIANI AND J. N ´ U˜ NEZ special attention to those in tubular surfaces, without accumulation and with all their vertices in one face. This paper comprises three sections besides this introduction. The first one is devoted to motivating the topic, showing the preliminary attempts to face the kinds of problems we are dealing here. The next section provides the reader with some useful, preliminary concepts and results, linking Halin’s theorem and Oubi˜na and Zucchello’s theorem for any surface, and trying to do the same with pseudosurfaces. Afterwards, we deal with the problem of outer-embeddings without accumulation points in different tubular surfaces, including some reflections about the topic and ideas for future research. 2. The interest of infinite graphs. Regarding infinite graphs, uncountable graphs are of scientific significance, but its interest is mainly theoretical (see, for example, [11, 38], where planar embeddings and outer-embeddings are, respectively, characterized). However, contrary to popular belief, countable (locally finite) graphs involve an intrinsic, practical interest, since they are useful to model increasing systems, especially those which are periodic. About the planarity of infinite graphs, Dirac and Schuster [19]proved that a countable graph is planar if and only if each finite subgraph is planar, and Wagner characterized in [38] all the planar graphs. But, as many authors have pointed out (see, for example, [24, 29, 30, 37]), it is advisable to add some supplementary properties to planarity in the case of infinite graphs. In particular, from a practical point of view, accumulation points must be avoided. Hence, Halin gave in [24]the characterization of (locally finite) graphs with a planar embedding and without vertex accumulation points (VAP-free planarity) in terms of forbidden subgraphs. And Thomassen introduced EAP-free planarity, showing that all connected VAP-free planar graphs admit locally finite planar representations such that the edge set has no accumulation point in the plane ([36]). Later, the complete set of EAP-free planar graphs was characterized in [6]. Other non-compact surfaces, different from the plane, also arouse some interest. In fact, the characterization of graphs admitting embeddings with no vertex accumulation point on tubular surfaces S(n) of finite genus was already found in [33]. This fact gives special rele- OUTERPLANARITY EXTENSION CONSEQUENCES 1075 vance to two research lines. On the one hand, VAP-free embeddability and EAP-free embeddability are closely related for every non-compact surface (see [14], to verify the relationship between VAP-free-S(n)and EAP-free-S(n) graphs). On the other hand, we should pay some extra attention to the graphs admitting embeddings with all their vertices in one face. These outerplanar embeddings have many practical and useful properties, above all, for the modeling of increasing systems (something also pointed out for general infinite graphs). Therefore, three typical fields of interest are architecture [35], printed circuit boards [28] or communication networks and routing [21], respectively. Simultaneously, outerplanarity has developed into a study of other compact surfaces and pseudosurfaces, as the Bananas surface [10]orothers[9]. Sometimes, only a few vertices are of interest to the future growth of the modeled system. Therefore, Oubi˜na and Zucchello introduced a concept very related to our aims. They defined and characterized in [32]theW-outerplanar graphs, where Wis any non-empty set of vertices of a graph G,Gis planar and each vertex of Wis on the boundary of the outer face. In this sense, we say that a graph is W-Sembeddable if it has an embedding in Ssuch that all the vertices of W are in the same face. Another step ahead for our infinite graphs is the analysis of infinite outerplanar graphs, and the first attempts to generalize outerplanar graphs to the case of infinite graphs were [8, 16]. They characterized some specific families of graphs with planar embeddings and without accumulation points. Since then, more papers about infinite graphs have been produced (see, for example, [11] with respect to uncountable graphs and [12] regarding countable graphs). As another consequence of the previously mentioned relations and of the important results about graph minors obtained by Robertson and Seymour in [34] (for any compact surface and for the spindle surface), it is proved that the minimal set of forbidden minors for graph embeddings with no vertex accumulation point in non-compact surfaces is finite, something that we are about to recall for infinite graphs. 3. Some basic concepts and results. All graphs in this paper will be considered undirected and without loops or multiple edges. We will use the standard graph-theoretical terminology, as it is presented 1076 L. BOZA, E.M. FEDRIANI AND J. N ´ U˜ NEZ FIGURE 1. The grid (left) has one unstable end, while the Euclidean line (right) has two stable ends. FIGURE 2. GW(right) is the strongly stable graph built from G(left); Wis the set of both distinguished vertices. in [25], except vertex instead of point and edge instead of line.When infinite graphs are considered, we use the terminology in [26, 27, 31]. When we deal with infinite graphs in this paper, we mean locally finite graphs with a countable vertex set, i.e., countable graphs such that the degree of any vertex is finite. The formal definition of an embedding for this kind of graphs in tubular surfaces can be consulted in [29, 30]. These tubular surfaces are built from a compact surface S,ofa finite genus, where nopen discs are replaced by nopen cylinders. For tubular surfaces of finite genus, we will use an invariant of noncompact spaces, namely Freudenthal end [22]. So, S(n)represents a non-compact surface of finite genus with nFreudental ends. For example, if S2is the sphere and P2is the projective plane, then S2(1) is homeomorphic to the plane, S2(2) is the open cylinder and P2(1) is homeomorphic to the M¨obius band. In addition, when Gis a graph we can use the following countable sequence G1⊆G2⊆ ··· of finite subgraphs to define the ends of G. An infinite ray in a graph Gis a morphism ψ:Pw→Ginducing an injection on both the vertex set and the edge set, where Pwrepresents a graph such that its underlying topological space is homeomorphic OUTERPLANARITY EXTENSION CONSEQUENCES 1077 to the positive half-line R+. Two infinite rays in Gdefine the same Freudenthal end if vertices exist in G−Hfor any subgraph Hof G.For example, the Euclidean half-line R+=[0,+∞) has one Freudenthal end and the Euclidean line has two. All Euclidean spaces Rn, with n≥2, have, exactly, one Freudenthal end. An end of a graph defined by Pwis said to be stable if any G−K (for any Kcompact in G) defined by Pwis a tree. Otherwise, the end is said to be unstable (see Figure 1). An interesting theorem about unstable ends can be found in [18]. We say that an end of a graph Gis strongly stable if a finite subgraph Hexists such that every component of G−His an infinite ray. If Gis a finite graph and Wis a set of vertices of G,wedenotebyGWto the strongly stable graph built from Gwith one infinite ray starting from every vertex of W(see Figure 2). Therefore, a graph Gis strongly stable if and only if Gand a subset of its vertices, W, exist such that Gis isomorphic to GW. However, we have other methods to obtain infinite graphs: In short, the way to characterize VAP-free-S(n) graphs is based on removing some points to make the graph non-compact (i.e., replacing an open disc from Sby an open cylinder and replacing an edge from the graph by an infinite ray). From now on, we denote this process by decompactification (see Figure 3). In general, one can apply a sequence of decompactifications (or a decompactification by npoints), but some extra difficulties emerge, as can be checked in [12]. If Gis a countable graph with all its nends strongly stable and admitting an embedding without accumulation points in tubular surface S(n), then it is possible to obtain some graph G∗from which Gis the decompactification of G∗by npoints. In general, such a graph G∗is not unique, since it depends upon the embedding chosen in G(moreover, it depends upon the “remaining” vertices of degree two after contracting each end). We define a main n-compactification when the rays are replaced by n vertices and one vertex of each ray remains. In 1966 Halin [24] already characterized VAP-free-S2(1) graphs in terms of forbidden subgraphs: Theorem 3.1 [24]. A planar graph is VAP-free if and only if it has no subgraph homeomorphic to K∞ 5,L∞ 3,3,K∞ 3,3or L∞ 5(see Figure 4). Clearly, if Gis a minor of Gand Gis VAP-free-S(n), then Gis VAPfree-S(n). In this way, the characterization of the VAP-free-S(n) graphs 1078 L. BOZA, E.M. FEDRIANI AND J. N ´ U˜ NEZ FIGURE 3. Decompactification of K3,3in a vertex (left) and in an inner point of an edge (right). uu uuu uu - L∞ 5 uu uu uu K∞ 3,3 u uu uuu- K∞ 5 uu uu uu - L∞ 3,3 uu- uu u u -  - FIGURE 4. Halin’s graphs. FIGURE 5. (G2,W 2)R1(G1,W 1): subgraph. OUTERPLANARITY EXTENSION CONSEQUENCES 1079 FIGURE 6. (G2,W 2)R2(G1,W 1): contracting edge xin w. can be given in terms of forbidden minors. We denote by KVAP (S(n)) the set of forbidden VAP-free-S(n)minors. AgraphGis in KVAP (S(n)) if it is not VAP-free-S(n), and it verifies that if His a minor of Gand Gis not a minor of Hthen His VAP-free-S(n). The explicit characterization of graph embeddings with no vertex accumulation point in the M¨obius band was independently obtained by Revuelta [33] and Archdeacon, et al. [3]; they gave the list of forbidden minors for VAP-free-P2(1)-embeddability. In the following, we are going to prove that there exists an equivalence between one infinite-type problem and one finite-type problem. In this way, we will allow the characterization of VAP-free-Sembeddings (a generalization of Theorem 3.1) for any compact surface S.Butwe need some previous results related to W-S-embeddable graphs. First, in order to enunciate Oubi˜na and Zucchello’s theorem (see [32]formore details), we define some elementary relationships on the set Lof pairs (G, W), where Gis a graph and Wis a set of vertices of G(in the corresponding figures, the vertices in this set Wwill be marked). 1. (G2,W 2)R1(G1,W 1)ifG1is a subgraph of G2,W1is a subset of W2and (G1,W 1)=(G2,W 2)(seeFigure5). 2. (G2,W 2)R2(G1,W 1)ifG1is obtained from G2by contracting an edge x={u, v}in a new vertex wand •if u, v /∈W2,thenW1is W2,and •if {u, v}∩W2=∅,thenW1=(W2∩V(G1)) ∪{w}(Figure 6). 3. (G2,W 2)R3(G1,W 1)ifv∈W2exists such that G1=G2−vand W1is the union of W2and the set of adjacent vertices of v(Figure 7). 1080 L. BOZA, E.M. FEDRIANI AND J. N ´ U˜ NEZ FIGURE 7. (G2,W 2)R3(G1,W 1): deleting vertex v∈W2. FIGURE 8. (K4,V(K4)) (left) and (K2,3,{a, b, c}) (right). Now we are able to define the relation >i,fori=1,2, in the following way: let (G, W )and(G,W) be two arbitrary elements of L. We will say that (G, W)>i(G,W) if a sequence of elements of Lexists, (G1,W 1),(G2,W 2),... ,(Gn,W n), with (G1,W 1)=(G, W) and (Gn,W n)=(G,W) such that (Gk,W k)Rhk(Gk+1,W k+1), with hk∈{1,2,... ,i+1},foreachk=1,2,... ,n−1. We will also denote by (G, W)≥i(G,W)if(G, W)=(G,W)or(G, W )>i(G,W). Obviously, if (G, W)>1(G,W), then (G, W)>2(G,W). Besides, ≥1is closely related to the minor ordering and ≥2is also related to the YΔordering (see [5], for example, for a detailed description of these orderings). The above introduced relation is interesting to us because Oubi˜na and Zucchello’s theorem can be re-formulated in the following way: Theorem 3.2 [32]. A graph Gis not W-outerplanar if and only if (G, W)≥2(K4,V(K4)) or (G, W)≥2(K2,3,{a, b, c}),wherea,band care vertices of K2,3with degree 2(Figure 8). By using this result, it is easy to check the following: OUTERPLANARITY EXTENSION CONSEQUENCES 1081 FIGURE 9. (K5−K2,{a, b})(left)and(K3,3−K2,{c, d}) (right). Corollary 3.3 A graph Gis not W-outerplanar if and only if (G, W)≥1(K4,V(K4)),(G, W)≥1(K2,3,{a, b, c}),wherea,band care the vertices of K2,3with degree 2,(G, W)≥1(K5−K2,{a, b}), where aand bare the vertices of K5−K2with degree 3,or(G, W)≥1 (K3,3−K2,{a, b}),whereaand bare the vertices of K3,3−K2with degree 2(Figures 8and 9). Oubi˜na and Zucchello’s theorem presents the characterization of the W-S2-embeddable graphs and C´aceres gave in [15] the characterization of the W-P2-embeddable graphs. Now we can provide the reader with some properties for the general compact surface S. Later, we will consider the case of pseudosurfaces (at the end of this section). It is easy to check that, if (G, W)Rk(G,W)(withk=1,2,3) and Gis W-S-embeddable, then Gis W-S-embeddable. Thus, if (G, W)>i(G,W)(withi=1,2) and Gis W-S-embeddable, then G is W-S-embeddable and the characterization of the W-S-embeddable graphs can be given in terms of minimal elements of Lin the order >i, in the sense that (G, W) is minimal if Gis non-W-S-embeddable and if (G, W)>i(G,W), then Gis W-S-embeddable. We denote by Li(S), with i=1,2, the set of minimal elements in the order >i. Hence, L2(S2)is{(K4,V(K4)),(K2,3,{a, b, c})},where a,band care the vertices of K2,3with degree 2 (Figure 8), and L1(S2) is L2(S2)∪{(K5−K2,{a, b}),(K3,3−K2,{c, d})},whereaand bare the vertices of K5−K2with degree 3, and cand dare the vertices of K3,3−K2with degree 2 (Figure 9). In this sense, we can state that C´aceres found in [15] the set of minimal elements of L1(P2)and L2(P2). It is obvious that a relationship exists between the infinite graphs that have a planar embedding with no vertex accumulation point, charac- 1088 L. BOZA, E.M. FEDRIANI AND J. N ´ U˜ NEZ 3. D. Archdeacon, C.P. Bonnington, M. Debowsky and M. Prestidge, Halin’s theorem for the M¨obius strip,ArsCombin.68 (2003), 243 256. 4. D. Archdeacon, C.P. Bonnington and J. ˇ Sir´aˇn, Halin’s theorem for cubic graphs on an annulus, Discrete Math. 281 (2004), 13 25. 5. D. Archdeacon, N. Hartsfield, C.H.C. Little and B. Mohar, Obstruction sets for outer-projective-planar graphs,ArsCombin.49 (1998), 113 127. 6. R. Ayala, E. Dom´ınguez, A. M´arquez and A. Quintero, On the graphs which are the edge of a plane tiling, Math. Scand. 77 (1995), 5 16. 7. C.P. Bonnington and R.B. Richter, Graphs embedded in the plane with finitely many accumulation points, Res. Rep. 472 (2001), Dept. of Mathematics, University of Auckland. 8. L. Boza, A. Di´anez and A. M´arquez, On infinite outerplanar graphs,Math. Bohem. 119 (1994), 381 384. 9. L. Boza, E.M. Fedriani and J. N´u˜nez, The problem of outer embeddings in pseudosurfaces,ArsCombin.71 (2004), 79 91. 10. ,Obstruction sets for outer-bananas-surface graphs,ArsCombin.73 (2004), 65 77. 11. ,Uncountable graphs with all their vertices in one face,ActaMath. Hungar. 112 (2006), 307 313. 12. ,Outer-embeddings and coloration of graph ends,toappear. 13. ,Outerplanarity without accumulation in the cylinder and the M¨obius band,toappear. 14. L.Boza,A.M´arquez and P. Revuelta, Embedding graphs without edge accumulation points in tubular surfaces,ArsCombin.82 (2007), 223 235. 15. J. C´aceres, Diversos tipos de planaridad de grafos, Ph.D. thesis, Dpto. de Geometr´ıa y Topolog´ıa, Universidad de Almer´ıa, 1996. 16. J. C´aceres and A. M´arquez, W-p-outerplanar graphs, Congres. Numeran. 104 (1994), 113 116. 17. G. Chartrand and F. Harary, Planar permutation graphs, Annal. Instit. Henri Poincar´e Probab. Statist. 3(1967), 433 438. 18. R. Diestel, A short proof of Halin’s grid theorem, Abh. Math. Sem. Univ. Hamburg, Seminar der Universit¨at Hamburg 74 (2004), 237 242. 19. G.A. Dirac and S. Schuster, A theorem of Kuratowski, Indag. Math. 16 (1954), 343 348. 20. E.M. Fedriani, Inmersiones de grafos en superficies y seudosuperficies con todos los v´ertices en una misma cara, Ph.D. thesis, Dpto. de Geometr´ıa y Topolog´ıa, Universidad de Sevilla, 2001. Available at: http://fondosdigitales.us.es/tesis/ tesis/1505/inmersiones-de-grafos-en-superficies-y-seudosuperficies-contodos-los-vertices-en-una-misma-cara/ 21. G.N. Frederickson and R. Janardan, Space-eficient and fault-tolerant routing in outerplanar graphs, IEEE: Trans. on Comp. 37 (1988), 1529 1540. 22. H. Freudenthal, ¨ Uber die Enden Topologischer Ra¨ume und Gruppen,Math. Z. 33 (1931), 692 713. OUTERPLANARITY EXTENSION CONSEQUENCES 1089 23. H.H. Glover, J.P. Huneke and C.S. Wang, 103 graphs that are irreducible for the projective plane,J.Combin.Theory27 (1979), 332 370. 24. H. Halin, Zur H¨aufungspunktfreien Darsellung Adz¨ahlbarer Graphen in der Ebene,Arch.Math.17 (1966), 239 242. 25. F. Harary, Graph theory, Addison Wesley, Reading, MA, 1969. 26. D. K¨onig, Theorie der endlichen und endlichen Graphen, Akad. Verlag., Leipzig (1936). Reprinted by Chelsea, New York, 1950. 27. K. Kuratowski, Sur le probl`eme des courbes gauches en topologie, Fund. Math. 15 (1930), 271 283. 28. M.C. van Lier and R.H.J.M. Otten, C.A.D. of masks and wiring, Tech. Rep. 74-e-44, Dept. Elect. Eng., Eindhoven University of Technology, The Netherlands, 1974. 29. B. Mohar, Embeddings of infinite graphs, J. Combin. Theory 44 (1988), 29 43. 30. B. Mohar and C. Thomassen, Graphs on surfaces, The Johns Hopkins University Press, London, 2001. 31. C.St.J.A. Nash-Williams, Infinite graphs A survey,J.Combin.Theory3 (1967), 286 301. 32. L. Oubi˜na and R. Zucchello, A generalization of outerplanar graphs,Discr. Math. 51 (1984), 243 249. 33. M.P. Revuelta, Inmersiones de grafos en superficies tubulares de g´enero finito, Ph.D. thesis, Dpto. de Matem´atica Aplicada I, Universidad de Sevilla, Spain, 1999. 34. N. Robertson and P.D. Seymour, Graph minors VIII. A Kuratowski theorem for general surfaces, J. Combin. Theor. 48 (1990), 255 288. 35. D.F. Robinson and I. Janjic, The constructability of floorplans with given outerplanar adjacency and room areas,ArsCombin.20 (1985), 133 142. 36. C. Thomassen, Straightline representations of infinite planar graphs,J. London Math. Soc. 16 (1977), 411 423. 37. ,Infinite graphs,inSelected topics in graph theory,Vol.2,Academic Press, 1983. 38. K. Wagner, Fastpl¨attbare Graphen, J. Combin. Theor. 3(1967), 326 365. Departamento de Matem´ atica Aplicada I, Universidad de Sevilla, Avda. Reina Mercedes 2, 41012, Sevilla, Spain Email address: b[email protected] Departamento de Econom ´ ıa, M´ etodos Cuantitativos e Historia Econ´ omica, Universidad Pablo de Olavide, Ctra. de Utrera, km 1. 41013, Sevilla, Spain Email address: [email protected] Departamento de Geometr´ ıa y Topolog ´ ıa, Universidad de Sevilla, Apdo. 1160. 41080, Sevilla, Spain Email address: jnva[email protected]