From: Bill Dubuque
Newsgroups: sci.math,comp.theory,sci.logic
Subject: Kuratowski planarity: generalizations [was: Electric, Water, Gas connection puzzler]
Date: 17 Nov 1996 07:59:42 -0500
Keywords: Kuratowski planarity, forbidden subgraphs, Jordan Curve theorem,
Robertson-Seymour theorem, Kruskal theorem, well-quasi-order, metamathematics,
van-Kampen obstructions, Whitney trick, nonconstructive complexity theory
"Bob Johannsen" writes:
>
> The problem is to connect each utility to each house, without crossing
> wires (pipes) or making connections house to house:
>
> Electric Water Gas
>
> House 1 House 2 House 3
>
> I don't think this can be done.
> But how can one prove this is impossible (if it is!)?
This graph is known as the complete bipartite graph K[3,3]. It is a
celebrated theorem of Kuratowski (1929) that a graph is planar iff it
contains no subgraph homeomorphic to the "forbidden subgraphs" K[3,3]
or K[5], the 5-vertex complete graph. This theorem was also proven earlier
in 1927-28 by Pontryagin, and later by Frink and Smith in 1930; see the
paper by Kennedy and Quintas for the history (a bibliography is below).
The fact that K[3,3] is nonplanar is the easy part of Kuratowski's theorem.
Thomassen has constructed a proof of the Jordan curve theorem based upon
this (see his 1992 Monthly paper), as well as short graph-theoretical proofs
of the the Jordan-Schonflies theorem, Hurwitz's theorem, etc., see his
1994 survey paper.
A far reaching generalization was obtained by Robertson and Seymour
in a long series of papers published during the eighties. They proved
that the collection of finite graphs is well-quasi-ordered by minor
embeddability, from which it follows that Kuratowski's "forbidden
minor" embedding obstruction generalizes to higher genus surfaces:
for a fixed integer g >= 0, there is a finite list of graphs L(g)
with the property that a graph C embeds on a surface of genus g
iff it does not contain, as a minor, any of the graphs on the list L.
Such techniques provide nonconstructive existence proofs of poly-time
algorithms for related graph-theoretic problems, in stark contrast to
the fact that most all earlier problems shown to be poly-time were
shown so by explicit constructions. This has interesting ramifications
in the foundations of complexity theory -- a topic which has been
discussed at length in a series of papers by Fellows and Langston.
Friedman has performed a metamathematical analysis of the
Robertson-Seymour theorem and has determined that it is independent
of some rather strong logical systems. See Simpson's excellent
expository survey for an introduction to this circle of ideas
(available online, see below). A similar analysis had already been
done for the weaker Kruskal theorem about embedding of trees -- which
has powerful applications to proving termination of rewrite rule
systems and the correctness of the Knuth-Bendix equational completion,
see Gallier's survey.
There has also been some work on higher-dimensional generalizations
of Kuratowski graphs, starting with a 1932 paper of van Kampen which
presents an obstruction o(K^n) which measures the nonembeddability of
an n-dim complex in R^(2n). This paper anticipated and stimulated later
developments in cohomology. It was ultimately shown by Wu and Shapiro
that, for n >= 3, K^n embeds in R^(2n) if o(K^n)=0, a result obtained
using the Whitney trick. A 1994 paper of Freedman et. al. shows that
the criterion is insufficient for n=2 (this paper also summarizes
related work since van Kampen). Sarkaria 1991 showed that the Whitney
trick may also be applied in the one dimensional case to thus obtain
Kuratowski's graph planarity criterion. See also Larmore's paper, and
Wu's book on embedding theory.
Following are some entry points into the literature. See the Monthly
papers for introductory expositions.
-Bill Dubuque
Even, Shimon
Graph algorithms.
Computer Software Engineering Series.
Computer Science Press, Inc., Woodland Hills, Calif., 1979. ix+249 pp. $17.95.
ISBN 0-914894-21-8 MR 82e:68066 68E10 05C99 94C15
Fellows, Michael R. (1-ID)
The Robertson-Seymour theorems: a survey of applications.
Graphs and algorithms (Boulder, CO, 1987), 1--18, Contemp. Math., 89,
Amer. Math. Soc., Providence, RI, 1989. MR 90k:05067 05C10 05A99 68R05 68R10
Fellows, Michael R. (1-ID); Langston, Michael A. (1-WAS)
Nonconstructive tools for proving polynomial-time decidability.
J. Assoc. Comput. Mach. 35 (1988), no. 3, 727--739.
MR 90i:68046 68Q25 03D15 68R10
Fellows, Michael R. (3-VCTR-C); Kaschube, Paul A.
Searching for $K\sb {3,3}$ in linear time.
Linear and Multilinear Algebra 29 (1991), no. 3-4, 279--290.
MR 92i:05084 05C10 05C85 68R10
Freedman, Michael H. (1-UCSD); Krushkal, Vyacheslav S. (1-UCSD);
Teichner, Peter (1-UCSD)
van Kampen's embedding obstruction is incomplete for $2$-complexes
in ${\bf R}\sp 4$.
Math. Res. Lett. 1 (1994), no. 2, 167--176. MR 95c:57005 57M20 57Q35
Friedman, Harvey (1-OHS); Robertson, Neil (1-OHS); Seymour, Paul (1-BELL6)
The metamathematics of the graph minor theorem.
Logic and combinatorics (Arcata, Calif., 1985), 229--261,
Contemp. Math., 65, Amer. Math. Soc., Providence, R.I., 1987.
MR 88g:03085 03F35 05C10
Gallier, Jean
What's so special about Kruskal's theorem and the ordinal Gamma[0]?
A survey of some results in proof theory,
Ann. Pure and Applied Logic, 53 (1991) 199-260.
[HFR] Harrington, L.A. et.al. (editors)
Harvey Friedman's Research on the Foundations of Mathematics.
Elsevier 1985.
Kennedy, John W. (1-PACE); Quintas, Louis V. (1-PACE);
Sys\lo, Maciej M. (PL-WROC-C)
The theorem on planar graphs. (English. French, Polish summary)
Historia Math. 12 (1985), no. 4, 356--368. MR 87e:01025 01A60 05C10
Larmore, Lawrence L.
The first obstruction to embedding a $1$-complex in $2$-manifold.
Illinois J. Math. 14 1970 1--11. MR 40#4955 55.70 (Reviewer: C. W. Patty)
Ne\v set\v ril, Jaroslav (CS-CHRL); Thomas, Robin (CS-CHRL)
Well quasi-orderings, long games and a combinatorial study of undecidability.
Logic and combinatorics (Arcata, Calif., 1985), 281--293,
Contemp. Math., 65, Amer. Math. Soc., Providence, R.I., 1987.
MR 88i:03098 03F35 03D55 03E05 03F30 05C05 90D99
Sarkaria, K. S. (6-PUNJ)
A one-dimensional Whitney trick and Kuratowski's graph planarity criterion.
Israel J. Math. 73 (1991), no. 1, 79--89. MR 92g:57034 57Q35 55S35
Simpson, Stephen G.
Unprovable theorems and fast-growing functions.
Contemporary Math. 65 1987, 359-394.
ftp://swiss-ftp.ai.mit.edu/incoming/unprovable.txt
\v Sirá\v n, Jozef (CS-STU); Gvozdjak, Pavol (CS-KMSK)
Kuratowski-type theorems do not extend to pseudosurfaces.
J. Combin. Theory Ser. B 54 (1992), no. 2, 209--212. MR 93a:05056 05C10
Smorynski, Craig (all three papers are reprinted in [HFR])
Some rapidly growing functions. Math. Intell., 2 1980, 149-154.
The Varieties of Arboreal Experience. Math. Intell., 4 1982, 182-188.
"Big" News from Archimedes to Friedman. Notices AMS, 30 1983, 251-256.
Spencer, Joel
Large numbers and unprovable theorems.
Amer. Math. Monthly, Dec 1983, 669-675.
Thomassen, Carsten (DK-TUD)
Embeddings of graphs.
Graphs and combinatorics (Qawra, 1990).
Discrete Math. 124 (1994), no. 1-3, 217--228.
MR 95f:05035 05C10 05C25 20F32 57M15
Thomassen, Carsten (DK-TUD)
The Jordan-Schonflies theorem and the classification of surfaces.
Amer. Math. Monthly 99 (1992), no. 2, 116--130.
MR 92k:57026 57M99 05C10 57N05 57Q15
Thomassen, Carsten
Kuratowski's theorem.
J. Graph Theory 5 (1981), no. 3, 225--241. MR 83d:05039 05C10
Thomassen, Carsten (1-PA)
A link between the Jordan curve theorem and the Kuratowski planarity criterion.
Amer. Math. Monthly 97 (1990), no. 3, 216--218. MR 91g:55005 55M99 05C10
Wilf, Herbert S. (1-PA)
Finite lists of obstructions.
Amer. Math. Monthly 94 (1987), no. 3, 267--271. MR 88d:05055 05C10
W. J. Wu
A theory of imbedding, immersion, and isotopy of polytopes in a Euclidean
space, Science Press, Peking, 1965; MR 35 #6146