Characterizing Planarity Using Theta Graphs 1 Dan Archdeacon1 and Josef Širáň2 DEPARTMENT OF MATHEMATICS AND STATISTICS UNIVERSITY OF VERMONT BURLINGTON, VT, USA 05405 E-mail: dan.archdeacon@uvm.edu 2 DEPARTMENT OF MATHEMATICS FACULTY OF CIVIL ENGINEERING SLOVAK TECHNICAL UNIVERSITY 813 68 BRATISLAVA, SLOVAKIA E-mail: siran@lux.svf.stuba.sk Received June 6, 1996 Abstract: A theta graph is a homeomorph of K2,3 . In an embedded planar graph the local rotation at one degree-three vertex of a theta graph determines the local rotation at the other degree-three vertex. Using this observation, we give a characterization of planar graphs in terms of balance in an associated signed graph whose vertices are K1,3 c 1998 John Wiley & Sons, Inc. J Graph subgraphs and whose edges correspond to theta graphs. Theory 27: 17–20, 1998 Keywords: planar graphs, Kuratowski, signed graphs 1. INTRODUCTION Planar graphs are one of the most important and interesting classes in graph theory. We have recently made an observation which has led to a simple and elegant characterization of planar graphs. In this paper we present this characterization and a few related topics. We begin with the basic definitions. Our graphs are allowed to have multiple edges. We forbid loops, as they do not seem to add to our theory and serve to complicate the statement of some results. We divide each edge into two half-edges corresponding to the two ends of the edge. A claw in the graph is a set of three pairwise adjacent half-edges. We say the claw is rooted at the c 1998 John Wiley & Sons, Inc. CCC 0364-9024/98/010017-04 18 JOURNAL OF GRAPH THEORY common incident vertex. In the literature, a claw sometimes means an induced K1,3 ; here we only take the root and the three incident half-edges and do not care about adjacencies between the other vertices. A theta graph is one homeomorphic to K2,3 , or equivalently, a pair of distinct vertices joined by three pairwise internally-vertex-disjoint paths. A theta graph contains exactly two claws rooted at the two degree-three vertices. Given a graph G we form the (simple) triple graph T = T (G) whose vertex set is all claws of G and whose edge set joins two claws whenever they lie in a common theta subgraph of G. A signature on a graph is an assignment of a plus or minus sign on each edge. A signed graph is a graph together with a signature. A cycle in a signed graph is balanced or unbalanced according to whether it contains an even or odd number of negative edges respectively. A local switch on a signed graph reverses the sign of each edge incident with a vertex. Observe that a local switch does not change the balance of any cycle. Two signed graphs are equivalent if there is a sequence of local switches transforming one signature into the other. Any signature is equivalent to one where the edges in a fixed spanning tree T are all signed positive. A signed graph is balanced if every cycle is balanced. If the edges of T are all positive in a balanced signature, then every co-tree edge is also positive. Hence a balanced graph is equivalent to one signed with every edge positive. There are exactly two embeddings of a theta graph into an oriented plane corresponding to the two ways to consistently locally orient the plane. These embeddings can be described in terms of local rotations: cyclic permutations of the half-edges incident with a vertex induced by a consistent orientation on the plane. Beginning with a planar embedding of a theta graph, reversing the local rotation at exactly one degree-three vertex results in a non-planar embedding. The signed triple graph T ± (G) of a graph G is formed as follows. The vertex set of T ± (G) is again the claws of G. Arbitrarily fix a local rotation on each claw. Join two claws with a positive edge if they lie in a common theta and their local rotations embed this theta in the plane. Join two claws with a negative edge if they lie in a common non-planar theta. Observe that T ± (G) may have multiple edges, but only if they have different signs. As stated, the graph T ± (G) is not well defined because it depends on the local rotation to each claw of G. But reversing this local rotation toggles the sign of each edge incident with the corresponding vertex, so the two signatures on T ± (G) are equivalent. 2. THE CHARACTERIZATION We offer now our main result. Theorem 2.1. G is planar if and only if the signed triple graph T ± (G) is balanced. Proof. To prove the necessity, suppose that G is embedded in an oriented plane. The orientation of the plane induces a local rotation on each claw. If two claws lie in a common theta, then these local rotations correspond to the given planar embedding. Hence every edge in T ± (G) is positive, i.e., the graph is balanced. To prove the sufficiency we need two observations. First, if H is a subgraph of G, then T ± (H) is a signed subgraph of T ± (G). We will use this in the form that if T ± (H) is unbalanced, then T ± (G) is also unbalanced. Second, if H is homeomorphic to K, then T ± (H) is signed isomorphic to T ± (K). PLANARITY AND THETA GRAPHS 19 Kuratowski’s Theorem [2] states that a graph is non-planar if and only if it contains a subgraph homeomorphic to K3,3 or to K5 . By the comments in the preceding paragraph our proof is complete when we show that T ± (K3,3 ) and T ± (K5 ) are both unbalanced. Let the vertex set of K3,3 be {a, b, c} ∪ {1, 2, 3}, where each letter is adjacent to each number. There is a unique claw on each vertex. There are exactly two theta graphs containing the claw on a and the claw on 1: the first uses paths a2b1, a3c1, a1 and the second uses paths a2c1, a3b1, a1. Regardless of the local rotations on these claws, one theta graph corresponds to a planar embedding while the other theta graph corresponds to a non-planar embedding. Hence there is an unbalanced cycle of length 2 in T ± (K3,3 ). Let the vertex set of K5 be {0, 1, 2, 3, 4}. We will find an unbalanced cycle of length 4 with the first three edges positive. Without loss of generality let the claw rooted at 0 with half-edges to 2, 3, and 4 have local rotation 234. There is a theta with this claw and a claw rooted at 2 using paths 042,02,032. Using a local switch if necessary, we can assume that this edge is positive. This implies that the claw at 2 has local rotation 043. There is a theta from this claw at 2 to a claw at 1 using paths 201,241,231. Switching so that this edge is positive, the claw at 1 has local rotation 340. Using a theta with paths 103,13,143 which corresponds to a positive edge, we get a claw at 3 with local rotation 410. But the theta 3120,30,340 joins this last claw with our first claw. The local rotations give a non-planar embedding, so this edge is minus. This is our desired unbalanced 4-cycle. This completes the proof of our main result. 3. CONCLUSION It would be interesting to use T (G) or T ± (G) to prove other results about G. The following is one example. Proposition 3.1. Let G be a simple graph of minimum degree at least three. Then G is 3connected if and only if T (G) is connected. Proof. Suppose that G is the union of two subgraphs H1 and H2 which meet along exactly two vertices. Partition the claws into two classes C1 and C2 depending on whether at least two of their half-edges lie in H1 or H2 respectively. Each class is non-empty and no edge in T (G) joins C1 to C2 , so T (G) is disconnected. A similar argument holds if G is disconnected or has a cutpoint, so one implication is shown. Our proof of the converse uses induction on the number of edges. To start the induction we observe that T (K4 ) = K4 is connected. For the inductive step, we need a theorem of Rademacher and Steinitz. They showed [3] that any 3-connected graph G 6= K4 contains an edge e = uv such that the graph G0 formed from G − e by smoothing any degree-two vertices is also 3-connected. With such an edge, a vertex in T (G) − T (G0 ) corresponds to a claw rooted at either u or v and using one of the half-edges in e. Let c be such a claw rooted at u using half-edges to v, 1, 2. Since G0 is 3-connected, G0 − v is 2-connected, and so there exists a cycle C of G0 − v using the edges 1u and u2. Let P be a path from u through v which intersects C in a vertex w 6= u, v. Then C ∪ P forms a theta graph containing c as one claw and some c0 ∈ T (G0 ) rooted at w as the other claw. Hence every vertex of T (G) − T (G0 ) is adjacent to one in T (G0 ). By our inductive hypothesis T (G0 ) is connected, and thus T (G) is also. Corollary 3.1. A 3-connected planar graph has a unique planar embedding. 20 JOURNAL OF GRAPH THEORY Proof. Since T (G) is connected so is T ± (G). It follows that there are at most two ways to get all edges of T (G) positive. These correspond to the two orientations of the plane in the given embedding, so that embedding must be unique. This corollary is commonly called Whitney’s Theorem [6]. It is easy to prove Whitney’s Theorem directly from Rademacher and Steinitz' Theorem without using the signed triple graph. Nevertheless, we thought that this was an interesting connection. The authors tried to find a ‘‘theta proof’’ of Kuratowski’s Theorem, but abandoned the effort when it appeared that our proof would be at least as complicated as those already in the literature. We hope that the reader will be more successful. The graph T ± (G) has proven useful in analysing planarity where there are some additional restrictions on the rotations, in particular, where one local rotation determines another. These embeddings arose in the study of when certain topological spaces embed in 3-space. We refer the reader to [1] for details. Our approach is also related to the work of Robertson, Seymour, and Thomas on Kuratowski Chains [4] related to linkless embeddings of graphs in 3-space. ACKNOWLEDGMENTS Dan Archdeacon gratefully thanks the Slovak Technical University and the University of Auckland, both of which hosted him during the time when this research was completed. References [1] D. Archdeacon, C. P. Bonnington, R. B. Richter, and J. Širáň, Sewing ribbons on graphs in space, in preparation. [2] K. Kuratowski, Sur le probleme de courbes gauches en topologie, Fund. Math. 15 (1930), 271–283. [3] H. Rademacher and E. Steinitz, Vorlesungen über die Theorie der Polyeder, Springer, Berlin (1934). [4] N. Robertson, P. D. Seymour, and R. Thomas, Kuratowski chains, J. Combin. Theory S. B 64 (1995), 127–154. [5] W. T. Tutte, Connectivity of graphs, Oxford University Press, London (1966). [6] H. Whitney, Non-separable and planar graphs, Trans. Amer. Math. Soc. 34 (1932), 339–362.

1/--страниц