Graph Drawing: 14th International Symposium, GD 2006, Karlsruhe, Germany, September 18-20, 2006. Revised Papers

Emo Welzl (auth.), Michael Kaufmann, Dorothea Wagner (eds.)3540709037, 9783540709039

This book constitutes the thoroughly refereed post-proceedings of the 14th International Symposium on Graph Drawing, GD 2006, held in Karlsruhe, Germany in September 2006.The 33 revised full papers and 5 revised short papers presented together with 2 invited talks, 1 system demo, 2 poster papers and a report on the graph drawing contest were carefully selected during two rounds of reviewing and improvement from 91 submissions. All current aspects in graph drawing are addressed ranging from foundational and methodological issues to applications for various classes of graphs in a variety of fields.

---

Table of contents :
Front Matter….Pages –
The Number of Triangulations on Planar Point Sets….Pages 1-4
The Algorithmic Beauty of Digital Nature….Pages 5-7
Integrating Edge Routing into Force-Directed Layout….Pages 8-19
Multipole-Based Force Approximation Revisited – A Simple but Fast Implementation Using a Dynamized Enclosing-Circle-Enhanced k-d-Tree….Pages 20-29
SSDE: Fast Graph Drawing Using Sampled Spectral Distance Embedding….Pages 30-41
Eigensolver Methods for Progressive Multidimensional Scaling of Large Data….Pages 42-53
Angle and Distance Constraints on Tree Drawings….Pages 54-65
Schematisation of Tree Drawings….Pages 66-76
Trees with Convex Faces and Optimal Angles….Pages 77-88
Three-Dimensional Drawings of Bounded Degree Trees….Pages 89-94
Simultaneous Graph Embedding with Bends and Circular Arcs….Pages 95-107
Embedding Graphs Simultaneously with Fixed Edges….Pages 108-113
Drawing Cubic Graphs with at Most Five Slopes….Pages 114-125
Planarity Testing and Optimal Edge Insertion with Embedding Constraints….Pages 126-137
Open Rectangle-of-Influence Drawings of Inner Triangulated Plane Graphs….Pages 138-149
Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor….Pages 150-161
On the Crossing Number of Almost Planar Graphs….Pages 162-173
On the Decay of Crossing Numbers….Pages 174-183
How Important Is the “Mental Map”? – An Empirical Investigation of a Dynamic Graph Layout Algorithm….Pages 184-195
Computing Geometric Minimum-Dilation Graphs Is NP-Hard….Pages 196-207
Chordal Graphs as Intersection Graphs of Pseudosegments….Pages 208-219
Parameterized st -Orientations of Graphs: Algorithms and Experiments….Pages 220-233
Straight-Line Drawing of Quadrangulations….Pages 234-239
Visualizing Large and Clustered Networks….Pages 240-251
Partitioned Drawings….Pages 252-257
Path Simplification for Metro Map Layout….Pages 258-269
Minimizing Intra-edge Crossings in Wiring Diagrams and Public Transportation Maps….Pages 270-281
Upright-Quad Drawing of st -Planar Learning Spaces….Pages 282-293
Choosing Colors for Geometric Graphs Via Color Space Embeddings….Pages 294-305
Morphing Planar Graphs in Spherical Space….Pages 306-317
k -Colored Point-Set Embeddability of Outerplanar Graphs….Pages 318-329
Thickness of Bar 1-Visibility Graphs….Pages 330-342
A New Approximation Algorithm for Bend Minimization in the Kandinsky Model….Pages 343-354
Radial Drawings of Graphs: Geometric Constraints and Trade-Offs….Pages 355-366
Characterization of Unlabeled Level Planar Trees….Pages 367-379
Drawing Bipartite Graphs on Two Curves….Pages 380-385
Improved Circular Layouts….Pages 386-398
Controllable and Progressive Edge Clustering for Large Networks….Pages 399-404
Biclique Edge Cover Graphs and Confluent Drawings….Pages 405-416
Schnyder Woods and Orthogonal Surfaces….Pages 417-429
Partitions of Graphs into Trees….Pages 430-439
The Website for Graph Visualization Software References (GVSR)….Pages 440-441
Smoother Transitions Between Breadth-First-Spanning-Tree-Based Drawings….Pages 442-445
Fast Node Overlap Removal—Correction….Pages 446-447
Graph-Drawing Contest Report….Pages 448-452
Back Matter….Pages –