Graph Drawing: 12th International Symposium, GD 2004, New York, NY, USA, September 29-October 2, 2004, Revised Selected Papers (Lecture Notes in Computer Science, 3383)

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. 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 l 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 - Constitutes the refereed post-proceedings of the 12th International Symposium on Graph Drawing, GD 2004, held in New York, NY, USA in September/October 2004. This book addresses various aspects in graph drawing, ranging from foundational and methodological issues to applications for various classes of graphs in a variety of fields.