Graph Drawing

Graphdrawingaddressestheproblemofconstructingrepresentationsofabstract graphs, networks, and hypergraphs. The 6th Symposium on Graph Drawing (GD 98) was held August 13{15, 1998,atMcGillUniversity,Montr eal,Canada.ItimmediatelyfollowedtheTenth Canadian Conference on Computational Geometry (CCCG 98), held August 10{12 at McGill. The GD 98 conference attracted 100 paid registrants from academic and industrial institutions in thirteen countries. Roughly half the p- ticipantsalsoattendedCCCG 98.Asinthepast,interactionamongresearchers, practitioners,andstudents fromtheoreticalcomputer science,mathematics,and the application areas of graph drawing continued to be an important aspect of the graph drawing symposium. In response to the call for papers and system demonstrations, the program committee received 57 submissions, of which 10 were demos. Each submission was reviewed by at least 4 members of the program committee, and comments were returnedto the authors.Following extensive email discussions andmultiple rounds of voting, the program committee accepted 23 papers and 9 demos. GD 98 also held an unrefereed poster gallery. The poster gallery contained 16 posters, 14 of which have abstracts in this volume. The poster gallery served to encourageparticipationfromresearchersinrelatedareasandprovidedast- ulating environment for the breaks between the technical sessions. In keeping with the tradition of previous graph drawing conferences, GD 98 held a graph drawing contest. This contest, which is traditionally a conference highlight,servestomonitorandtochallengethestateoftheartingraphdrawing. A report on the 1998 contest appears in this volume.

Includes supplementary material: sn.pub/extras

Inhalt
Papers.- Drawing of Two-Dimensional Irregular Meshes.- Quasi-Upward Planarity.- Three Approaches to 3D-Orthogonal Box-Drawings.- Using Graph Layout to Visualize Train Interconnection Data.- Difference Metrics for Interactive Orthogonal Graph Drawing Algorithms.- Upward Planarity Checking: Faces Are More than Polygons.- A Split&Push Approach to 3D Orthogonal Drawing.- Geometric Thickness of Complete Graphs.- Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs.- On Improving Orthogonal Drawings: The 4M-Algorithm.- Algorithmic Patterns for Orthogonal Graph Drawing.- A Framework for Drawing Planar Graphs with Curves and Polylines.- Planar Polyline Drawings with Good Angular Resolution.- A Layout Adjustment Problem for Disjoint Rectangles Preserving Orthogonal Order.- Drawing Algorithms for Series-Parallel Digraphs in Two and Three Dimensions.- Approximation Algorithms for Finding Best Viewpoints.- Level Planarity Testing in Linear Time.- Crossing Number of Abstract Topological Graphs.- Self-Organizing Graphs A Neural Network Perspective of Graph Layout.- Embedding Planar Graphs at Fixed Vertex Locations.- Proximity Drawings: Three Dimensions Are Better than Two.- NP-Completeness of Some Tree-Clustering Problems.- Refinement of Orthogonal Graph Drawings.- A Combinatorial Framework for Map Labeling.- An Algorithm for Three-Dimensional Orthogonal Graph Drawing.- System Demonstrations.- Graph Multidrawing: Finding Nice Drawings Without Defining Nice.- Edge Labeling in the Graph Layout Toolkit.- Improved Force-Directed Layouts.- A Fully Animated Interactive System for Clustering and Navigating Huge Graphs.- Drawing Large Graphs with H3Viewer and Site Manager.- Cooperation between Interactive Actions and Automatic Drawing in a Schematic Editor.-Visualization of Parallel Execution Graphs.- JIGGLE: Java Interactive Graph Layout Environment.- Contest.- Graph-Drawing Contest Report.- Poster Abstracts.- Implementation of an Efficient Constraint Solver for the Layout of Graphs in Delaunay.- Planar Drawings of Origami Polyhedra.- Human Perception of Laid-Out Graphs.- Ptolomaeus:The Web Cartographer.- Flexible Graph Layout and Editing for Commercial Applications.- Multidimensional Outlines Wordgraphs.- VisA: A Tool for Visualizing and Animating Automata and Formal Languages.- Elastic Labels on the Perimeter of a Rectangle.- VGJ: Visualizing Graphs Through Java.- A Library of Algorithms for Graph Drawing.- The Size of the Open Sphere of Influence Graph in L ? Metric Spaces.- Maximum Weight Triangulation and Graph Drawing.- Adding Constraints to an Algorithm for Orthogonal Graph Drawing.- On Computing and Drawing Maxmin-Height Covering Triangulation.