вход по аккаунту



код для вставкиСкачать
Characterizing Planarity
Using Theta Graphs
Dan Archdeacon1 and Josef Širáň2
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
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
1998 John Wiley & Sons, Inc.
CCC 0364-9024/98/010017-04
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
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.
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).
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.
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.
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.
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.
D. Archdeacon, C. P. Bonnington, R. B. Richter, and J. Širáň, Sewing ribbons on graphs in space, in
K. Kuratowski, Sur le probleme de courbes gauches en topologie, Fund. Math. 15 (1930), 271–283.
H. Rademacher and E. Steinitz, Vorlesungen über die Theorie der Polyeder, Springer, Berlin (1934).
N. Robertson, P. D. Seymour, and R. Thomas, Kuratowski chains, J. Combin. Theory S. B 64 (1995),
W. T. Tutte, Connectivity of graphs, Oxford University Press, London (1966).
H. Whitney, Non-separable and planar graphs, Trans. Amer. Math. Soc. 34 (1932), 339–362.
Без категории
Размер файла
87 Кб
Пожаловаться на содержимое документа