Roll over image to zoom in Click on image to zoom

Graphs on Surfaces

Name: Graphs on Surfaces
Brand: JOHNS HOPKINS UNIVERSITY PRESS
SKU: 9780801866890
Price: 210.0 AUD
Availability: InStock

JOHNS HOPKINS UNIVERSITY PRESSISBN: 9780801866890

Price:

$210.00

Stock:

Out of Stock - Available to backorder

Quantity:

By Bojan Mohar, Carsten Thomassen
Imprint: JOHNS HOPKINS UNIVERSITY PRESS
Release Date: August 14, 2001
Format: HARDBACK
Pages: 304

Share this product

Button Actions

Please copy the ISBN for submitting review copy form

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.

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

""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.""

Graphs on Surfaces

Request Academic Copy

Description

You may also like

Recently viewed