Algorithms for drawing planar graphs

Indeholder "Preface", "Contents", "A. Introduction", "1. Drawing Planar Graphs", "2. Backgrounds", " 2.1 Terminology", " 2.2 Testing and Embedding Planar Graphs", " 2.2.1 Introduction", " 2.2.2 Testing Planarity Using PQ-trees", " 2.2.3 Constructing Planar Embeddings Using PQ-trees", " 2.3

Show More

Planarization of Graphs", " 2.3.1 Introduction", " 2.3.2 Planarization Using PQ-trees", " 2.3.3 Maximal Planarization", " 2.4 Biconnected and Triconnected Components", " 2.4.1 The BC-tree", " 2.4.2 The SPQR-tree", " 2.5 The Canonical Ordering", " 2.6 Augmentation and Drawing Algorithms", "B. Augmenting Planar Graphs", "3. Introduction", "4. The Planar Biconnectivity Augmentation Problem", " 4.1 Preliminaries", " 4.2 NP-completeness", " 4.3 Approximation Within 2 Times Optimal", " 4.4 A Special Case", " 4.5 The Planar Bridge-Connectivity Augmentation Problem", "5. The Planar Triconnectivity Augmentation Problem", " 5.1 Preliminaries", " 5.2 An Approximation Algorithm", " 5.2.1 The Series Case", " 5.2.2 The Parallel Case", " 5.2.3 The Rigid Case", " 5.3 Triconnecting While Minimizing The Maximum Degree", "6. Triangulating Planar Graphs", " 6.1 NP-completeness", " 6.2 Triangulating While Minimizing the Maximum Degree", " 6.2.1 The Algorithm", " 6.2.2 Counting the Increase of deg(v)", "7. Augmenting Outerplanar Graphs", " 7.1 Introduction", " 7.2 Bridge-Connectivity", " 7.3 Biconnectivity", " 7.3.1 Stage 2", " 7.3.2 Stage 3", " 7.4 Triconnectivity", " 7.4.1 Triconnecting Biconnected Outerplanar Graphs", " 7.4.2 Triconnecting Outerplanar Graphs", " 7.5 Triangulating Outerplanar Graphs", " 7.5.1 Triangulating One Face of a Planar Graph", " 7.5.2 Triangulating Outerplanar Graphs", "8. Conclusions", "C. Drawing Planar Graphs", "9. Drawing Algorithms", " 9.1 Straight-line Drawings", " 9.2 Convex Drawings", " 9.3 Drawing Planar Graphs Using the st-Numbering", " 9.3.1 Visibility Representation", " 9.3.2 Orthogonal Drawings", " 9.4 Overview of Part C", "10. The Drawing Framework and Convex Drawings", " 10.1 The Drawing Framework", " 10.1.1 The lmc-Ordering", " 10.1.2 Computing the Coordinates", " 10.2 Convex Drawings", " 10.2.1 Convex Drawings on an (2n-4) * (n-2) Grid", " 10.2.2 Convex Drawings on an (n-2) * (n-2) Grid", " 10.3 Drawing d-Planar Graphs", " 10.4 Visibility Representations", " 10.5 Improvements of the lmc-Ordering", " 10.5.1 Duality Aspects", " 10.5.2 A New shift-Method", "11. Orthogonal Drawings", " 11.1 Orthogonal Drawings of 4-Planar Graphs", " 11.2 Orthogonal Drawings of 3-Planar Graphs", " 11.2.1 Triconnected 3-Planar Graphs", " 11.2.2 Drawing Biconnected 3-Planar Graphs", " 11.2.3 Drawing General 3-Planar Graphs Orthogonally", "12. Hexagonal Drawings", " 12.1 Triconnected 3-Planar Graphs", " 12.2 Drawing Graphs with Degree at most 3", " 12.3 Drawings with Straight Lines", " 12.4 Heuristics for Decreasing the Area", "13. Rectangular Duals", " 13.1 Introduction", " 13.2 The Rectangular Dual Algorithm", " 13.3 Computing a REL Using a Canonical Ordering", " 13.4 Algorithm for Visibility Representation", " 13.4.1 Compact Visibility Representations", "14. Conclusions", "Bibliography", "Index", "Samenvatting", "Curriculum Vitae".

Gennemgang af mange forskellige måder at tegne en planar graf. Ret sjov at læse selv om man ikke har brug for algoritmerne.

Show Less