Planar Graphs, Volume 32

1st Edition

Theory and Algorithms

Authors: T. Nishizeki N. Chiba
Hardcover ISBN: 9780444702128
eBook ISBN: 9780080867748
Imprint: North Holland
Published Date: 1st April 1988
Page Count: 231
72.95 + applicable tax
43.99 + applicable tax
54.95 + applicable tax
Unavailable
Compatible Not compatible
VitalSource PC, Mac, iPhone & iPad Amazon Kindle eReader
ePub & PDF Apple & PC desktop. Mobile devices (Apple & Android) Amazon Kindle eReader
Mobi Amazon Kindle eReader Anything else

Institutional Access


Table of Contents

Graph Theoretic Foundations. Some Basic Definitions. Planar Graphs. Euler's Formula. Kuratowski's Theorem. Dual Graphs. Bounds for Planar Graphs. Algorithmic Foundations. What is an Algorithm? Machine Model and Complexity. NP-Complete. Data Structure and Graph Representation. Exploring a Graph. Planarity Testing and Embedding. Planarity Testing. Embedding Algorithm. Drawing Planar Graphs. Convex Drawing. Convex Testing. Example. Vertex-Coloring. Proof of Five-Coloring Theorem and 0(n2) Algorithm. Batch Processing Algorithm. Sequential Processing Algorithm. Edge-Coloring. Algorithm COLOR. Algorithm ALCOLOR. Edge-Coloring Multigraphs. Independent Vertex Sets. Approximation Algorithm. Baker's Algorithm. Listing Subgraphs. Arboricity and Efficient Edge-Searching. Listing Triangles. Listing Quadrangles. Listing Maximal Cliques. Planar Separator Theorem. Applications of the Planar Separator Theorem. Maximum Matching. Minimum Vertex Cover. Hamiltonian Cycles. Proof of Tutte's Theorem. Algorithm and 0(n2) Bound. Hamiltonian Walk. Flows in Planar Graphs. Definition of Multicommodity Flows. Planar Single-Commodity Flow. Multicommodity Flows for C1. Multicommodity Flows for Ca. Bibliography. Index.

Description

Collected in this volume are most of the important theorems and algorithms currently known for planar graphs, together with constructive proofs for the theorems. Many of the algorithms are written in Pidgin PASCAL, and are the best-known ones; the complexities are linear or 0(nlogn).

The first two chapters provide the foundations of graph theoretic notions and algorithmic techniques. The remaining chapters discuss the topics of planarity testing, embedding, drawing, vertex- or edge-coloring, maximum independence set, subgraph listing, planar separator theorem, Hamiltonian cycles, and single- or multicommodity flows.

Suitable for a course on algorithms, graph theory, or planar graphs, the volume will also be useful for computer scientists and graph theorists at the research level. An extensive reference section is included.


Details

No. of pages:
231
Language:
English
Copyright:
© North Holland 1988
Published:
Imprint:
North Holland
eBook ISBN:
9780080867748
Hardcover ISBN:
9780444702128

Reviews

@qu:For many of the topics included, the present monograph is the first complete treatment in book form... will be useful not only for students but also for specialists in graph theory and computer science who are interested in the theory and algorithms for planar graphs. @source:Zentralblatt für Mathematik @from:D. Seese @qu:The monograph can be recommended for graduate students and researchers in computer sceince and graph theory. It is also useful for a course on algorithmic graph theory or planar graphs. @source:Biometrical Journal


About the Authors

T. Nishizeki Author

N. Chiba Author