Graph Drawing: 12th International Symposium, GD 2004, New York, NY, USA, September 29-October 2, 2004, Revised Selected Papers

Greg Aloupis, Prosenjit Bose, Pat Morin (auth.), János Pach (eds.)3540245286, 9783540245285

This book constitutes the thoroughly refereed post-proceedings of the 12th International Symposium on Graph Drawing, GD 2004, held in New York, NY, USA in September/October 2004.

The 39 revised full papers and 12 revised short papers presented together with 4 posters and a report on the graph drawing context were carefully selected during two rounds of reviewing and improvement. 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 –
Reconfiguring Triangulations with Edge Flips and Point Moves….Pages 1-11
Drawing Power Law Graphs….Pages 12-17
Hexagonal Grid Drawings: Algorithms and Lower Bounds….Pages 18-24
Improved Bounds for the Number of (≤ k )-Sets, Convex Quadrilaterals, and the Rectilinear Crossing Number of K n ….Pages 25-35
On the Realizable Weaving Patterns of Polynomial Curves in $mathbb R^3$ ….Pages 36-42
Drawing the AS Graph in 2.5 Dimensions….Pages 43-48
Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps….Pages 49-59
Convex Drawings of 3-Connected Plane Graphs….Pages 60-70
Partitions of Complete Geometric Graphs into Plane Trees….Pages 71-81
Additional PC-Tree Planarity Conditions….Pages 82-88
GraphML Transformation….Pages 89-99
Clustering Cycles into Cycles of Clusters….Pages 100-110
Unit Bar-Visibility Layouts of Triangulated Polygons….Pages 111-121
Really Straight Graph Drawings….Pages 122-132
Layouts of Graph Subdivisions….Pages 133-143
Label Number Maximization in the Slider Model….Pages 144-154
An Efficient Implementation of Sugiyama’s Algorithm for Layered Graph Drawing….Pages 155-166
Random Geometric Graph Diameter in the Unit Disk with ℓ p Metric….Pages 167-172
Algorithms for Drawing Media….Pages 173-183
Confluent Layered Drawings….Pages 184-194
Simultaneous Embedding of Planar Graphs with Few Bends….Pages 195-205
A Fast and Simple Heuristic for Constrained Two-Level Crossing Reduction….Pages 206-216
Contact and Intersection Representations….Pages 217-227
Dynamic Graph Drawing of Sequences of Orthogonal and Hierarchical Graphs….Pages 228-238
Graph Drawing by Stress Majorization….Pages 239-250
Computing Radial Drawings on the Minimum Number of Circles….Pages 251-261
Hamiltonian-with-Handles Graphs and the k -Spine Drawability Problem….Pages 262-272
Distributed Graph Layout for Sensor Networks….Pages 273-284
Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm….Pages 285-295
Building Blocks of Upward Planar Digraphs….Pages 296-306
A Linear Time Algorithm for Constructing Maximally Symmetric Straight-Line Drawings of Planar Graphs….Pages 307-317
Train Tracks and Confluent Drawings….Pages 318-328
The Three Dimensional Logic Engine….Pages 329-339
Long Alternating Paths in Bicolored Point Sets….Pages 340-348
Intersection Reverse Sequences and Geometric Applications….Pages 349-359
New Exact Results and Bounds for Bipartite Crossing Numbers of Meshes….Pages 360-370
Drawing Pfaffian Graphs….Pages 371-376
3D Visualization of Semantic Metadata Models and Ontologies….Pages 377-388
A Note on the Self-similarity of Some Orthogonal Drawings….Pages 389-394
No-Three-in-Line-in-3D….Pages 395-402
Visual Navigation of Compound Graphs….Pages 403-413
Layout Volumes of the Hypercube….Pages 414-424
New Theoretical Bounds of Visibility Representation of Plane Graphs….Pages 425-430
Visualizing Large Graphs with Compound-Fisheye Views and Treemaps….Pages 431-441
A Compound Graph Layout Algorithm for Biological Pathways….Pages 442-447
Curvilinear Graph Drawing Using the Force-Directed Method….Pages 448-453
Graphael: A System for Generalized Force-Directed Layouts….Pages 454-464
QUOGGLES: Query On Graphs – A Graphical Largely Extensible System….Pages 465-470
Visualisation of Large and Complex Networks Using PolyPlane ….Pages 471-481
The Metro Map Layout Problem….Pages 482-491
An Interactive Multi-user System for Simultaneous Graph Drawing….Pages 492-501
Gravisto : Graph Visualization Toolkit….Pages 502-503
DNA Secondary Structures for Probe Design….Pages 504-507
Open Problems Wiki….Pages 508-509
Visualization and ILOG CPLEX….Pages 510-511
Graph-Drawing Contest Report….Pages 512-516
Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth….Pages 517-533
Back Matter….Pages –