Overview

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-colour theorem stating that any map can be coloured using only four colours such that no two bordering countries have the same colour. Now graph theory is an area of its own. 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 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 colouring graphs on surfaces.

Full Product Details

Author:   Bojan Mohar (University of Ljubljana) ,  Carsten Thomassen (The Technical University of Denmark)
Publisher:   Johns Hopkins University Press
Imprint:   Johns Hopkins University Press
Volume:   10
Dimensions:   Width: 15.20cm , Height: 2.60cm , Length: 22.90cm
Weight:   0.544kg
ISBN:  

9780801866890

ISBN 10:   0801866898
Pages:   304
Publication Date:   27 September 2001
Recommended Age:   From 17
Audience:   College/higher education ,  Professional and scholarly ,  Undergraduate ,  Postgraduate, Research & Scholarly
Format:   Hardback
Publisher's Status:   Active
Availability:   Manufactured on demand  
We will order this item for you from a manufactured on demand supplier.

Table of Contents

Contents: Chapter 1. Introduction Basic Definition Trees and bipartite graphs Blocks ConnectivityChapter 2. Planar Graphs Planar graphs and the Jordan Curve Theorem The Jordan-Schonflies Theorem The Theorem of Kuratowski Characterizations of planar graphs 3-connected planar graphs Dual graphs Planarity algorithms Circle packing representations The Riemann Mapping Theorem The Jordan Curve Theorem and Kuratowski's Theorem in general topological spacesChapter 3. Surfaces Classification of surfacesRotation systemsEmbedding schemesThe genus of a graphClassification of noncompact surfacesChapter 4. Embeddings Combinatorially, Contractibility, of Cycles, and the Genus Problem Embeddings combinatoriallyCycles of embedded graphsThe 3-path-conditionThe genus of a graphThe maximum genus of a graphChapter 5. The Width of Embeddings Edge-width 2-flippings and uniqueness of LEW-embeddings Triangulations Minimal triangulations of a given edge-width Face-width Minimal embeddings of a given face-width Embeddings of planar graphs The genus of a graph with a given nonorientable embedding Face-width and surface minors Face-width and embedding flexibility Combinatorial properties of embedded graphs of large widthChapter 6. Embedding Extensions and Obstructions Forbidden subgraphs and forbidden minors Bridges Obstruction in a bridge 2-restricted embedding extensions The forbidden subgraphs for the projective plane The minimal forbidden subgraphs for general surfacesChapter 7. Tree-Width and the Excluded Minor Theorem Tree-width and the excluded grid theoremThe excluded minor theorem for any fixed surfaceChapter 8. Colorings of Graphs on Surfaces Planar graphs are 5-choosable The Four Color Theorem Color critical graphs and the Heawood formula Coloring in a few colors Graphs without short cycles Appendix A. The minmal forbidden subgraphs for the projective plane Appendix B. The unavoidable configurations in planar triangulations Bibliography Index

Reviews

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

<p> 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

Author Information

Bojan Mohar is a professor in the Department of Mathematics at the University of Ljubljana in Slovenia and a member of the Engineering Academy of Slovenia. Carsten Thomassen is a professor at the Mathematical Institute of the Technical University of Denmark, the editor-in-chief of the Journal of Graph Theory, and a member of the Royal Danish Academy of Sciences and Letters.

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions