Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003 Revised Papers

Matthew Dickerson, David Eppstein, Michael T. Goodrich, Jeremy Yu Meng (auth.), Giuseppe Liotta (eds.)3540208313, 9783540208310, 9783540245957

The 11th International Symposium on Graph Drawing (GD 2003) was held on September 21–24, 2003, at the Universit` a degli Studi di Perugia, Perugia, Italy. GD 2003 attracted 93 participants from academic and industrial institutions in 17 countries. In response to the call for papers, the program committee received 88 re- larsubmissionsdescribingoriginalresearchand/orsystemdemonstrations.Each submission was reviewed by at least 4 program committee members and c- ments were returned to the authors. Following extensive e-mail discussions, the program committee accepted 34 long papers (12 pages each in the proceedings) and 11 short papers (6 pages each in the proceedings). Also, 6 posters (2 pages each in the proceedings) were displayed in the conference poster gallery. In addition to the 88 submissions, the program committee also received a submission of special type, one that was not competing with the others for a time slot in the conference program and that collects selected open problems in graph drawing. The aim of this paper, which was refereed with particular care andUNCHANGEDtworoundsofrevisions,istostimulatefutureresearchinthe graph drawing community. The paper presents 42 challenging open problems in di?erentareasofgraphdrawingandcontainsmorethan120references.Although the length of the paper makes it closer to a journal version than to a conference extended abstract, we decided to include it in the conference proceedings so that it could easily reach in a short time the vast majority of the graph drawing community.

---

Table of contents :
Front Matter….Pages –
Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way….Pages 1-12
An Experimental Study of Crossing Minimization Heuristics….Pages 13-24
Stop Minding Your P’s and Q’s: Implementing a Fast and Simple DFS-Based Planarity Testing and Embedding Algorithm….Pages 25-36
Bounds and Methods for k -Planar Crossing Numbers….Pages 37-46
How Many Ways Can One Draw a Graph?….Pages 47-58
Two Results on Intersection Graphs of Polygons….Pages 59-70
Stretching of Jordan Arc Contact Systems….Pages 71-85
Noncrossing Hamiltonian Paths in Geometric Graphs….Pages 86-97
GraphAEL : Graph Animations with Evolving Layouts….Pages 98-110
Visualizing Related Metabolic Pathways in Two and a Half Dimensions….Pages 111-122
GoVisual for CASE Tools Borland Together ControlCenter and Gentleware Poseidon – System Demonstration….Pages 123-128
Area-Efficient Drawings of Outerplanar Graphs….Pages 129-134
A Framework for User-Grouped Circular Drawings….Pages 135-146
Fixed-Location Circular-Arc Drawing of Planar Graphs….Pages 147-158
A More Practical Algorithm for Drawing Binary Trees in Linear Area with Arbitrary Aspect Ratio….Pages 159-165
An Integer Programming Approach to Fuzzy Symmetry Detection….Pages 166-177
Barycentric Drawings of Periodic Graphs….Pages 178-189
Three-Dimensional Grid Drawings with Sub-quadratic Volume….Pages 190-201
Laying Out Iterated Line Digraphs Using Queues….Pages 202-213
Track Drawings of Graphs with Constant Queue Number….Pages 214-225
3D Visibility Representations of Complete Graphs….Pages 226-237
Drawing Series-Parallel Graphs on Restricted Integer 3D Grids….Pages 238-246
Nearly Optimal Three Dimensional Layout of Hypercube Networks….Pages 247-258
Graph Embedding with Minimum Depth and Maximum External Face….Pages 259-272
More Efficient Generation of Plane Triangulations….Pages 273-282
Planar Embeddings of Graphs with Specified Edge Lengths….Pages 283-294
BGPlay: A System for Visualizing the Interdomain Routing Evolution….Pages 295-306
GraphEx: An Improved Graph Translation Service….Pages 307-313
A Constrained, Force-Directed Layout Algorithm for Biological Pathways….Pages 314-319
Intersection-Free Morphing of Planar Graphs….Pages 320-331
Fixed Parameter Algorithms for one-sided crossing minimization Revisited….Pages 332-344
Experiments with the Fixed-Parameter Approach for Two-Layer Planarization….Pages 345-356
Characterizing Families of Cuts That Can Be Represented by Axis-Parallel Rectangles….Pages 357-368
Convex Drawing for c-Planar Biconnected Clustered Graphs….Pages 369-380
Layout of Directed Hypergraphs with Orthogonal Hyperedges….Pages 381-386
No-Bend Orthogonal Drawings of Subdivisions of Planar Triconnected Cubic Graphs….Pages 387-392
Radial Level Planarity Testing and Embedding in Linear Time….Pages 393-405
An Improved Approximation to the One-Sided Bilayer Drawing….Pages 406-418
Straight-Line Drawings of 2-Outerplanar Graphs on Two Curves….Pages 419-424
An Energy Model for Visual Graph Clustering….Pages 425-436
Simultaneous Graph Drawing: Layout Algorithms and Visualization Schemes….Pages 437-449
Axis-by-Axis Stress Minimization….Pages 450-459
Drawing Graphs with Nonuniform Nodes Using Potential Fields….Pages 460-465
Drawing Area-Proportional Venn and Euler Diagrams….Pages 466-477
Optimal Pants Decompositions and Shortest Homotopic Cycles on an Orientable Surface….Pages 478-490
Degree Navigator TM : The Journey of a Visualization Software….Pages 491-493
HexGraph: Applying Graph Drawing Algorithms to the Game of Hex….Pages 494-495
GLuskap : Visualization and Manipulation of Graph Drawings in 3-Dimensions….Pages 496-497
Web-Linkage Viewer: Drawing Links in the Web Based on a Site-Oriented Framework….Pages 498-499
The Puzzle Layout Problem….Pages 500-501
Visual Data Mining with ILOG Discovery….Pages 502-503
Graph Drawing Contest Report….Pages 504-508
Engineering and Visualizing Algorithms….Pages 509-513
Report on the Invited Lecture by Pat Hanrahan, Titled “On Being in the Right Space”….Pages 514-514
Selected Open Problems in Graph Drawing….Pages 515-539
Back Matter….Pages –