 322 pág.

Graph Theory

DisciplinaTeoria dos Grafos342 materiais1.556 seguidores
Pré-visualização50 páginas
K3;3 has girth 4,
each Ci contains at least four edges, so
16 = 4 ¢ 4 6 jC1j+ : : :+ jC4j
6 2 kK3;3k¡ jC0j
6 2 ¢ 9¡ 4 = 14 ;
It is one of the hidden beauties of planarity theory that two such
abstract and seemingly unintuitive results about generating sets in cy-
cle spaces as MacLane\u2019s theorem and Tutte\u2019s theorem 3.2.3 conspire to
produce a very tangible planarity criterion for 3-connected graphs:
Theorem 4.5.2. (Tutte 1963)
A 3-connected graph is planar if and only if every edge lies on at most
(equivalently: exactly) two non-separating induced cycles.
Proof . The forward implication follows from Propositions 4.2.10 and
(3.2.3)
(4.2.1)
(4.2.5)
(4.2.10) 4.2.1 (and Proposition 4.2.5 for the \u2018exactly two\u2019 version); the backward
implication follows from Theorems 3.2.3 and 4.5.1. \u2044
4.6 Plane duality 87
4.6 Plane duality
In this section we shall use MacLane\u2019s theorem to uncover another con-
nection between planarity and algebraic structure: a connection between
the duality of plane graphs, deflned below, and the duality of the cycle
and cut space hinted at in Chapters 1.9 and 3.5.
A plane multigraph is a pair G = (V;E) of flnite sets (of vertices planemultigraph
and edges, respectively) satisfying the following conditions:
(i) V µ R2;
(ii) every edge is either an arc between two vertices or a polygon
containing exactly one vertex (its endpoint);
(iii) apart from its own endpoint(s), an edge contains no vertex and
no point of any other edge.
We shall use terms deflned for plane graphs freely for plane multigraphs.
Note that, as in abstract multigraphs, both loops and double edges count
as cycles.
Let us consider the plane multigraph G shown in Figure 4.6.1. Let
us place a new vertex inside each face of G and link these new vertices
up to form another plane multigraph G\u2044, as follows: for every edge e of
G we link the two new vertices in the faces incident with e by an edge e\u2044
crossing e; if e is incident with only one face, we attach a loop e\u2044 to the
new vertex in that face, again crossing the edge e. The plane multigraph
G\u2044 formed in this way is then dual to G in the following sense: if we
apply the same procedure as above to G\u2044, we obtain a plane multigraph
very similar to G; in fact, G itself may be reobtained from G\u2044 in this way.
G\u2044
e\u2044e
G
Fig. 4.6.1. A plane graph and its dual
To make this idea more precise, let G = (V;E) and (V \u2044; E\u2044) be any
two plane multigraphs, and put F (G) =: F and F ((V \u2044; E\u2044)) =: F \u2044. We
call (V \u2044; E\u2044) a plane dual of G, and write (V \u2044; E\u2044) =: G\u2044, if there are planedual G\u2044
bijections
F !V \u2044
f 7! v\u2044(f)
E!E\u2044
e 7! e\u2044
V !F \u2044
v 7! f\u2044(v)
satisfying the following conditions:
(i) v\u2044(f) 2 f for all f 2 F ;
88 4. Planar Graphs
(ii) je\u2044 \Gj = j\u201de\u2044 \\u201dej = je\G\u2044j = 1 for all e 2 E;
(iii) v 2 f\u2044(v) for all v 2 V .
The existence of such bijections implies that both G and G\u2044 are con-
nected (exercise). Conversely, every connected plane multigraph G has
a plane dual G\u2044: if we pick from each face f of G a point v\u2044(f) as a
vertex for G\u2044, we can always link these vertices up by independent arcs
as required by condition (ii), and there is always a bijection V ! F \u2044
satisfying (iii) (exercise).
If G\u20441 and G
\u2044
2 are two plane duals of G, then clearly G
\u2044
1 \u2019 G\u20442; in fact,
one can show that the natural bijection v\u20441(f) 7! v\u20442(f) is a topological
isomorphism between G\u20441 and G
\u2044
2. In this sense, we may speak of the
plane dual G\u2044 of G.
Finally, G is in turn a plane dual of G\u2044. Indeed, this is witnessed
by the inverse maps of the bijections from the deflnition of G\u2044: setting
v\u2044(f\u2044(v)) := v and f\u2044(v\u2044(f)) := f for f\u2044(v) 2 F \u2044 and v\u2044(f) 2 V \u2044, we
see that conditions (i) and (iii) for G\u2044 transform into (iii) and (i) for G,
while condition (ii) is symmetrical in G and G\u2044. Thus, the term \u2018dual\u2019
is also formally justifled.
Plane duality is fascinating not least because it establishes a con-
nection between two natural but very difierent kinds of edge sets in a
multigraph, between cycles and cuts:
Proposition 4.6.1. For any connected plane multigraph G, an edge set[ 6.5.2 ]
E µ E(G) is the edge set of a cycle in G if and only if E\u2044 := f e\u2044 j e 2 E g
is a minimal cut in G\u2044.
Proof . By conditions (i) and (ii) in the deflnition of G\u2044, two vertices(4.1.1)(4.2.3)
v\u2044(f1) and v\u2044(f2) of G\u2044 lie in the same component of G\u2044¡ E\u2044 if and
only if f1 and f2 lie in the same region of R2r
S
E: every v\u2044(f1){v\u2044(f2)
path in G\u2044¡E\u2044 is an arc between f1 and f2 in R2r
S
E, and conversely
every such arc P (with P \V (G) = ;) deflnes a walk in G\u2044¡E\u2044 between
v\u2044(f1) and v\u2044(f2).
Now if C µ G is a cycle and E = E(C) then, by the Jordan curve
theorem and the above correspondence, G\u2044¡E\u2044 has exactly two com-
ponents, so E\u2044 is a minimal cut in G\u2044.
Conversely, if E µ E(G) is such that E\u2044 is a cut in G\u2044, then, by
Proposition 4.2.3 and the above correspondence, E contains the edges
of a cycle C µ G. If E\u2044 is minimal as a cut, then E cannot contain any
further edges (by the implication shown before), so E = E(C). \u2044
Proposition 4.6.1 suggests the following generalization of plane du-
ality to a notion of duality for abstract multigraphs. Let us call a multi-
graph G\u2044 an abstract dual of a multigraph G if E(G\u2044) = E(G) and theabstractdual
minimal cuts in G\u2044 are precisely the edge sets of cycles in G. Note that
any abstract dual of a multigraph is connected.
4.6 Plane duality 89
Proposition 4.6.2. If G\u2044 is an abstract dual of G, then the cut space
of G\u2044 is the cycle space of G, i.e.
C\u2044(G\u2044) = C(G) :
Proof . By Lemma 1.9.4,5 C\u2044(G\u2044) is the subspace of E(G\u2044) = E(G) (1.9.4)
generated by the minimal cuts in G\u2044. By assumption, these are precisely
the edge sets of the cycles in G, and these generate C(G) in E(G). \u2044
We flnally come to one of the highlights of classical planarity the-
ory: the planar graphs are characterized by the fact that they have an
abstract dual. Although less obviously intuitive, this duality is just as
fundamental a property as planarity itself; indeed the following theorem
may well be seen as a topological characterization of the graphs that
have a dual:
Theorem 4.6.3. (Whitney 1933)
A graph is planar if and only if it has an abstract dual.
Proof . Let G be a graph. If G is plane, then every component C of G has (1.9.3)(4.5.1)
a plane dual C\u2044. Let us consider these C\u2044 as abstract multigraphs, pick
a vertex in each of them, and identify these vertices. In the connected
multigraph G\u2044 obtained, the set of minimal cuts is the union of the sets
of minimal cuts in the multigraphs C\u2044. By Proposition 4.6.1, these cuts
are precisely the edge sets of the cycles in G, so G\u2044 is an abstract dual
of G.
Conversely, suppose that G has an abstract dual G\u2044. By Theorem
4.5.1 and Proposition 4.6.2 it su\u2013ces to show that C\u2044(G\u2044) has a simple
basis, which it has by Proposition 1.9.3. \u2044
Exercises
1. Show that every graph can be embedded in R3 with all edges straight.
2.¡ Show directly by Lemma 4.1.2 that K3;3 is not planar.
3.¡ Find an Euler formula for disconnected graphs.
4. Show that every connected planar graph with n vertices, m edges and
flnite girth g satisfles m 6 g
g¡2 (n¡ 2).
5. Show that every planar graph is a union of three forests.
5 Although the lemma was stated for graphs only, its proof remains the same for
multigraphs.
90 4. Planar Graphs
6. Let G1; G2; : : : be an inflnite sequence of pairwise non-isomorphic
graphs. Show that if lim sup &quot;(Gi) > 3 then the graphs Gi have un-
bounded genus|that is to say, there is no (closed) surface S in which
all the Gi can be embedded.
(Hint. You may use the fact that for every surface S there is a constant
´(S) 6 2 such that every graph embedded in S satisfles the generalized
Euler formula of n¡m+ \u2018 > ´(S).)
7. Find a direct proof for planar graphs of Tutte\u2019s theorem on the cycle
space of 3-connected