Planar Graphs (eBook)

Theory and Algorithms

N. Chiba, T. Nishizeki (Autoren)

eBook Download: PDF

1988 | 1. Auflage
231 Seiten
Elsevier Science (Verlag)
978-0-08-086774-8 (ISBN)

Infos

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.

Inhalt

Front Cover 1
Planar Graphs: Theory and Algorithms 4
Contents 8
Preface 12
Acknowledgments 14
Chapter 1. Graph Theoretic Foundations 16
1.1. Introduction 16
1.2. Some basic definitions 17
1.3. Planar graphs 21
1.4. Euler’s formula 24
1.5. Kuratowski’s theorem 26
1.6. Dual graphs 30
1.7. Bounds for planar graphs 34
Chapter 2. Algorithmic Foundations 38
2.1. What is an algorithm? 38
2.2. Machine model and complexity 39
2.3. NP-complete 40
2.4. Data structure and graph representation 42
2.5. Exploring a graph 44
Chapter 3. Planarity Testing and Embedding 48
3.1. Introduction 48
3.2. Planarity testing 49
3.3. Embedding algorithm 64
Chapter 4. Drawing Planar Graphs 80
4.1. Introduction 80
4.2. Convex drawing 81
4.3. Convex testing 85
4.4. Example 95
Chapter 5. Vertex-Coloring 98
5.1. Introduction 98
5.2. Proof of the five-coloring theorem and the O(n2) algorithm 99
5.3. Batch processing algorithm 102
5.4. Sequential processing algorithm 110
Chapter 6. Edge-Coloring 114
6.1. Introduction 114
6.2. Algorithm COLOR 115
6.3. Algorithm ALCOLOR 119
6.4. Edge-coloring multigraphs 128
Chapter 7. Independent Vertex Sets 136
7.1. Introduction 136
7.2. Approximation algorithm 137
7.3. Baker’s algorithm 149
Chapter 8. Listing Subgraphs 152
8.1. Introduction 152
8.2. Arboricity and efficient edge-searching 153
8.3. Listing triangles 155
8.4. Listing quadrangles 157
8.5. Listing maximal cliques 159
Chapter 9. Planar Separator Theorem 164
9.1. Introduction 164
9.2. Preliminary 164
9.3. Planar separator theorem 166
9.4. Applications of the planar separator theorem 175
9.5. Maximum matching 179
9.6. Minimum vertex cover 183
Chapter 10. Hamiltonian Cycles 186
10.1. Introduction 186
10.2. Proof of Tutte’s theorem 187
10.3. Algorithm and O(n2) bound 197
10.4. Hamiltonian walk 199
Chapter 11. Flows in Planar Graphs 200
11.1. Introduction 200
11.2. Definition of multicommodity flows 201
11.3. Planar single-commodity flow 204
11.4. Multicommodity flows for C1 206
11.5Multicommodity flows for Ca 225
References 236
Index 242

Produkt-Details

• Erscheint lt. Verlag: 1.4.1988
• Sprache: englisch
• Themenwelt: Informatik ► Software Entwicklung ► User Interfaces (HCI)
• Themenwelt: Informatik ► Theorie / Studium ► Algorithmen
• Themenwelt: Mathematik / Informatik ► Mathematik ► Graphentheorie
• Themenwelt: Naturwissenschaften
• Themenwelt: Technik
• ISBN-10: 0-08-086774-X / 008086774X
• ISBN-13: 978-0-08-086774-8 / 9780080867748