Literatur

1

S. Even: Graph Algorithms, Chapter 8: Testing Graph Planarity, Pitman 1979

2

T. Nishizeki, N. Chiba: Planar Graphs: Theory and Algorithms, Chapter 3: Planarity Testing and Embedding, North-Holland Mathematics Studies 140, Elsevier, 1988

3

C. Hundack, K. Mehlhorn, S. Näher: A simple linear time algorithm for identifying Kuratowski subgraphs of non-planar graphs, Technischer Report, 1996

4

N. Chiba, T. Nishizeki: A Linear Algorithm for Embedding Planar Graphs Using PQ-Trees, Journal of Computer and System Sciences, 30, 54-76, 1985

5

T. Nishizeki, N. Chiba: Planar Graphs: Theory and Algorithms, Chapter 5: Vertex-Coloring North-Holland Mathematics Studies 140, Elsevier, 1988

6

G. N Frederickson: On Linear-Time Algorithms for Five-Coloring Planar Graphs, Information Processing Letters 19, 1984, 219 - 224

7

T. Nishizeki, N. Chiba: Planar Graphs: Theory and Algorithms, Chapter 7: Independent Vertex Sets North-Holland Mathematics Studies 140, Elsevier, 1988

8

T. Emden-Weinert, St. Hougardy, B. Kreuter, H. J. Prömel, A. Steger: Einführung in Graphen und Algorithmen, Kapitel 8: Seperatoren, Skriptum, Humboldt-Universität zu Berlin, 1996

9

R. J. Lipton, R. E. Tarjan: A Seperator Theorem for Planar Graphs, SIAM Journal on Applied Mathematics, Vol. 36, No. 2, 177 - 189, 1979

10

R. J. Lipton, R. E. Tarjan: Applications of a Planar Seperator Theorem, SIAM Journal on Computing, Vol. 9, No. 3, 615 - 617, 1980

11

R. Bar-Yehuda, S. Even: On Approximating a Vertex Cover for Planar Graphs, 14th Symp. on the Theory of Computing (STOC), 1982, 303 - 309