Graph Drawing: 11th International Symposium, GD 2003, Perugia, Italy, September 21-24, 2003, Revised Papers (Lecture Notes in Computer Science, 2912)

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 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 -

This book constitutes the thoroughly refereed post-proceedings of the 11th International Symposium on Graph Drawing, GD 2003, held in Perugia, Italy, in September 2003.

The 34 revised full papers and 11 revised short papers presented were carefully selected during two rounds of reviewing and improvement. Also included are 6 posters, a report on the 2003 graph drawing contest, 2 invited contributions, as well as a comprehensive survey article presenting 42 challenging open problems in the area. The papers are organized in topical sections on planarity and planar drawings; geometric graph theory; application and systems; straight-line, circular, and circular-arc drawings; symmetrics; 3D-drawings; embeddings and triangulations; fixed parameter tractability; clusters, cuts, and orthogonal drawings; k-level drawings; force-directed and energy-based techniques; and surfaces and diagrams.

In most graph visualization applications, graphs are often drawn in a standard way: the vertices of a graph are drawn as simple shapes, such as circles or boxes, and the edges are drawn as individual curves connecting pairs of these shapes (e.g., see [12,13,22]).