Planar Graphs (eBook)
231 Seiten
Elsevier Science (Verlag)
978-0-08-086774-8 (ISBN)
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.
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.
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
| Erscheint lt. Verlag | 1.4.1988 |
|---|---|
| Sprache | englisch |
| Themenwelt | Informatik ► Theorie / Studium ► Algorithmen |
| Mathematik / Informatik ► Mathematik ► Graphentheorie | |
| Naturwissenschaften | |
| Technik | |
| ISBN-10 | 0-08-086774-X / 008086774X |
| ISBN-13 | 978-0-08-086774-8 / 9780080867748 |
| Haben Sie eine Frage zum Produkt? |
PDF (Adobe DRM)Größe: 9,6 MB
Kopierschutz: Adobe-DRM
Adobe-DRM ist ein Kopierschutz, der das eBook vor Mißbrauch schützen soll. Dabei wird das eBook bereits beim Download auf Ihre persönliche Adobe-ID autorisiert. Lesen können Sie das eBook dann nur auf den Geräten, welche ebenfalls auf Ihre Adobe-ID registriert sind.
Details zum Adobe-DRM
Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen eine
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen eine
Geräteliste und zusätzliche Hinweise
Zusätzliches Feature: Online Lesen
Dieses eBook können Sie zusätzlich zum Download auch online im Webbrowser lesen.
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
aus dem Bereich
