+612 9045 4394
Graphs on Surfaces : Johns Hopkins Studies in the Mathematical Sciences - Bojan Mohar

Graphs on Surfaces

Johns Hopkins Studies in the Mathematical Sciences


Published: 29th June 2001
For Ages: 22+ years old
Ships: 7 to 10 business days
7 to 10 business days
or 4 easy payments of $38.38 with Learn more

Graph theory is one of the fastest growing branches of mathematics. Until recently, it was regarded as a branch of combinatorics and was best known by the famous four-color theorem stating that any map can be colored using only four colors such that no two bordering countries have the same color. Now graph theory is an area of its own with many deep results and beautiful open problems. Graph theory has numerous applications in almost every field of science and has attracted new interest because of its relevance to such technological problems as computer and telephone networking and, of course, the internet. In this new book in the Johns Hopkins Studies in the Mathematical Science series, Bojan Mohar and Carsten Thomassen look at a relatively new area of graph theory: that associated with curved surfaces.

Graphs on surfaces form a natural link between discrete and continuous mathematics. The book provides a rigorous and concise introduction to graphs on surfaces and surveys some of the recent developments in this area. Among the basic results discussed are Kuratowski's theorem and other planarity criteria, the Jordan Curve Theorem and some of its extensions, the classification of surfaces, and the Heffter-Edmonds-Ringel rotation principle, which makes it possible to treat graphs on surfaces in a purely combinatorial way. The genus of a graph, contractability of cycles, edge-width, and face-width are treated purely combinatorially, and several results related to these concepts are included. The extension by Robertson and Seymour of Kuratowski's theorem to higher surfaces is discussed in detail, and a shorter proof is presented. The book concludes with a survey of recent developments on coloring graphs on surfaces.

As major players in an active field, the authors never make a wrong move: they choose the right topics, treat them to the right depth, rethink the classical arguments when appropriate, and anticipate the reader's questions. Any undergraduate who penetrates even two or three chapters will learn a great deal of important mathematics, and rather painlessly at that. Surely a classic. * Choice *

Prefacep. ix
Introductionp. 3
Basic definitionsp. 3
Trees and bipartite graphsp. 8
Blocksp. 10
Connectivityp. 11
Planar graphsp. 17
Planar graphs and the Jordan Curve Theoremp. 18
The Jordan-Schonflies Theoremp. 25
The Theorem of Kuratowskip. 30
Characterizations of planar graphsp. 33
3-connected planar graphsp. 39
Dual graphsp. 42
Planarity algorithmsp. 49
Circle packing representationsp. 51
The Riemann Mapping Theoremp. 64
The Jordan Curve Theorem and Kuratowski's Theorem in general topological spacesp. 66
Surfacesp. 77
Classification of surfacesp. 78
Rotation systemsp. 87
Embedding schemesp. 91
The genus of a graphp. 94
Classification of noncompact surfacesp. 95
Embeddings combinatorially, contractibility of cycles, and the genus problemp. 99
Embeddings combinatoriallyp. 99
Cycles of embedded graphsp. 103
The 3-path conditionp. 110
The genus of a graphp. 112
The maximum genus of a graphp. 122
The width of embeddingsp. 129
Edge-widthp. 129
2-flippings and uniqueness of LEW-embeddingsp. 135
Triangulationsp. 139
Minimal triangulations of a given edge-widthp. 142
Face-widthp. 146
Minimal embeddings of a given face-widthp. 154
Embeddings of planar graphsp. 159
The genus of a graph with a given nonorientable embeddingp. 163
Face-width and surface minorsp. 165
Face-width and embedding flexibilityp. 167
Combinatorial properties of embedded graphs of large widthp. 177
Embedding extensions and obstructionsp. 183
Forbidden subgraphs and forbidden minorsp. 184
Bridgesp. 185
Obstructions in a bridgep. 189
2-restricted embedding extensionsp. 195
The forbidden subgraphs for the projective planep. 197
The minimal forbidden subgraphs for general surfacesp. 202
Tree-width and the excluded minor theoremp. 205
Tree-width and the excluded grid theoremp. 205
Minimal obstructions of bounded tree-widthp. 215
The excluded minor theorem for any fixed surfacep. 218
Colorings of graphs on surfacesp. 223
Planar graphs are 5-choosablep. 223
The Four Color Theoremp. 225
Color critical graphs and the Heawood formulap. 230
Coloring in few colorsp. 235
Graphs without short cyclesp. 242
The minimal forbidden subgraphs for the projective planep. 247
The unavoidable configurations in planar triangulationsp. 253
Bibliographyp. 265
Indexp. 283
Table of Contents provided by Syndetics. All Rights Reserved.

ISBN: 9780801866890
ISBN-10: 0801866898
Series: Johns Hopkins Studies in the Mathematical Sciences
Audience: Professional
For Ages: 22+ years old
Format: Hardcover
Language: English
Number Of Pages: 304
Published: 29th June 2001
Publisher: Johns Hopkins University Press
Country of Publication: US
Dimensions (cm): 22.9 x 15.2  x 2.6
Weight (kg): 0.54