Graph Drawing

The 13th International Symposium on Graph Drawing (GD 2005) was held in Limerick, Ireland, September 12-14, 2005. One hundred and ?fteen participants from 19 countries attended GD 2005. In response to the call for papers the Program Committee received 101 subm- sions, each detailing original research or a system demonstration. Each submission was reviewed by at least three Program Committee members; each referee's c- ments were returned to the authors. Following extensive discussions, the comm- tee accepted 38 long papers, 3 short papers and 3 long system demos, each of which were presented during one of the conference's 12 sessions. Eight posters were also accepted and were on display throughout the conference. Two invited speakers, Kurt Mehlhorn and George Robertson, gave fascinating talks during the conference. Prof. Mehlhorn spoke on the use of minimum cycle bases for reconstructing surfaces, while Dr. Robertson gave a perspective, past and present, on the visualization of hierarchies. As is now traditional, a graph drawing contest was held during the conference. The accompanying report, written by Stephen Kobourov, details this year's c- test. This year a day-long workshop, organized by Seok-Hee Hong and Dorothea Wagner, was held in conjunction with the conference. A report on the "Workshop on Network Analysis and Visualization," written by Seok-Hee Hong, is included in the proceedings.

Inhalt

Papers.- Crossings and Permutations.- Morphing Planar Graphs While Preserving Edge Directions.- Dynamic Spectral Layout of Small Worlds.- Exact Crossing Minimization.- On Embedding a Cycle in a Plane Graph.- On Rectilinear Duals for Vertex-Weighted Plane Graphs.- Bar k-Visibility Graphs: Bounds on the Number of Edges, Chromatic Number, and Thickness.- Drawing K n in Three Dimensions with One Bend Per Edge.- Small Area Drawings of Outerplanar Graphs.- Volume Requirements of 3D Upward Drawings.- How to Embed a Path onto Two Sets of Points.- Upward Spirality and Upward Planarity Testing.- Graph Treewidth and Geometric Thickness Parameters.- Stress Majorization with Orthogonal Ordering Constraints.- Fast Node Overlap Removal.- Delta-Confluent Drawings.- Transversal Structures on Triangulations, with Application to Straight-Line Drawing.- A Hybrid Model for Drawing Dynamic and Evolving Graphs.- Two Trees Which Are Self-intersecting When Drawn Simultaneously.- C-Planarity of Extrovert Clustered Graphs.- Non-planar Core Reduction of Graphs.- An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs.- Hierarchical Layouts of Directed Graphs in Three Dimensions.- Layout Effects on Sociogram Perception.- On Edges Crossing Few Other Edges in Simple Topological Complete Graphs.- On Balloon Drawings of Rooted Trees.- Convex Drawings of Plane Graphs of Minimum Outer Apices.- Energy-Based Clustering of Graphs with Nonuniform Degrees.- A Mixed-Integer Program for Drawing High-Quality Metro Maps.- Crossing Number of Toroidal Graphs.- Drawing Graphs Using Modular Decomposition.- Applications of Parameterized st-Orientations in Graph Drawing Algorithms.- Complexity Results for Three-Dimensional Orthogonal Graph Drawing.- On Extending a Partial Straight-Line Drawing.- Odd Crossing Number Is Not Crossing Number.- Minimum Depth Graph Embeddings and Quality of the Drawings: An Experimental Analysis.- No-bend Orthogonal Drawings of Series-Parallel Graphs.- Parallel-Redrawing Mechanisms, Pseudo-Triangulations and Kinetic Planar Graphs.- Proper and Planar Drawings of Graphs on Three Layers.- Incremental Connector Routing.- An Application of Well-Orderly Trees in Graph Drawing.- Software Demonstrations.- GEOMI: GEOmetry for Maximum Insight.- WhatsOnWeb: Using Graph Drawing to Search the Web.- Drawing Clustered Graphs in Three Dimensions.- Posters.- BLer: A Boundary Labeller for Technical Drawings.- D-Dupe: An Interactive Tool for Entity Resolution in Social Networks.- A New Method for Efficiently Generating Planar Graph Visibility Representations.- SDE: Graph Drawing Using Spectral Distance Embedding.- MultiPlane: A New Framework for Drawing Graphs in Three Dimensions.- Visualizing Graphs as Trees: Plant a Seed and Watch it Grow.- On Straightening Low-Diameter Unit Trees.- Mixed Upward Planarization - Fast and Robust.- Workshop on Network Analysis and Visualisation.- Network Analysis and Visualisation.- Graph Drawing Contest.- Graph-Drawing Contest Report.- Invited Talks.- Minimum Cycle Bases and Surface Reconstruction.- Hierarchy Visualization: From Research to Practice.