Graph Drawing

This book constitutes the thoroughly refereed post-proceedings of the 7th International Symposium on Graph Drawing, GD '99, held in Stirin Castle, Czech Republic, in September 1999. The 38 revised full papers presented together with three invited contributions, two posters, and a report on the graph drawing contest were carefully reviewed and selected from 59 submissions. Among the topics addressed are orthogonality, levels, clusters, drawing, planarity, applications, symmetry, representations, and proximity and trees.

The range of issues considered in graph drawing includes algorithms, graph theory, geometry, topology, order theory, graphic languages, perception, app- cations, and practical systems. Much research is motivated by applications to systems for viewing and interacting with graphs. The interaction between th- retical advances and implemented solutions is an important part of the graph drawing eld. The annually organized graph drawing symposium is a forum for researchers, practitioners, developers, and users working on all aspects of graph visualization and representations. The preceding symposia were held in M- treal (GD'98), Rome (GD'97), Berkeley (GD'96), Passau (GD'95), Princeton (GD'94), and Paris (GD'93). The Seventh International Symposium on Graph Drawing GD'99 was or- nized at Sti r n Castle, in the vicinity of Prague, Czech Republic. This baroque castle recently restored as a hotel and conference center provided a secluded place for the participants, who made good use of the working atmosphere of the conference. In total the symposium had 83 registered participants from 16 countries.

Includes supplementary material: sn.pub/extras

Inhalt
Invited Talk.- The Anatomy of a Geometric Algorithm.- Orthogonality I.- Turn-Regularity and Planar Orthogonal Drawings.- Combining Graph Labeling and Compaction.- Almost Bend-Optimal Planar Orthogonal Drawings of Biconnected Degree-3 Planar Graphs in Quadratic Time.- Fully Dynamic 3-Dimensional Orthogonal Graph Drawing.- Levels I.- An E log E Line Crossing Algorithm for Levelled Graphs.- Level Planar Embedding in Linear Time.- Higres Visualization System for Clustered Graphs and Graph Algorithms.- Clusters I.- Partitioning Approach to Visualization of Large Graphs.- Graph Clustering Using Distance-k Cliques.- Drawing I.- A Framework for Circular Drawings of Networks.- Drawing Planar Graphs with Circular Arcs.- Drawing Graphs in the Hyperbolic Plane.- Invited Talk.- Graph Planarity and Related Topics.- Planarity.- Grid Drawings of Four-Connected Plane Graphs.- Graph Embedding with Topological Cycle-Constraints.- Embedding Vertices at Points: Few Bends Suffice for Planar Graphs.- The Constrained Crossing Minimization Problem.- Clusters II.- Planarity-Preserving Clustering and Embedding for Large Planar Graphs.- An Algorithm for Drawing Compound Graphs.- Levels II.- The Vertex-Exchange Graph: A New Concept for Multi-level Crossing Minimisation.- Using Sifting for k-Layer Straightline Crossing Minimization.- On 3-Layer Crossings and Pseudo Arrangements.- Applications.- Visualizing Algorithms for the Design and Analysis of Survivable Networks.- LayoutShow: A Signed Applet/Application for Graph Drawing and Experimentation.- Centrality in Policy Network Drawings.- Straight-Line Drawings of Protein Interactions.- Invited Talk.- Art of Drawing.- Symmetry.- An Heuristic for Graph Symmetry Detection.- Isomorphic Subgraphs.- Orthogonality II.- Orthogonal and Quasi-upwardDrawings with Vertices of Prescribed Size.- Multi-dimensional Orthogonal Graph Drawing with Small Boxes.- Representations.- Geometric Realization of Simplicial Complexes.- Visibility Representations of Complete Graphs.- Triangle-Free Planar Graphs as Segments Intersection Graphs.- Drawing II.- A Force-Directed Algorithm that Preserves Edge Crossing Properties.- Proximity and Trees.- Rectangle of Influence Drawings of Graphs without Filled 3-Cycles.- Voronoi Drawings of Trees.- Infinite Trees and the Future.- Latour A Tree Visualisation System.- Graph Drawing Contest.- Graph-Drawing Contest Report.- Hunting Down Graph B.- Posters.- Orthogonal and Straight-Line Drawings of Graphs with Succinct Representations.- Electronic Biochemical Pathways.