Graph Drawing: 6th International Symposium, GD '98 Montreal, Canada, August 13-15, 1998 Proceedings (Lecture Notes in Computer Science, 1547)

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. Graph Drawing Preface Drawing of Two-Dimensional Irregular Meshes Introduction Terminology Transforming Vertically Convex Meshes Context-Invariant Transformations Achieving Bounded Path Lengths Acknowledgements References Quasi-Upward Planarity Introduction Preliminaries Quasi-Upward Planarity Lower Bounds on the Number of Bends of Quasi-Upward Planar Drawings Computing Optimal Drawings with Branch and Bound Techniques Experimental Results Conclusions and Open Problems References Three Approaches to 3D-Orthogonal Box-Drawings* Introduction Existing Results Our Results Preliminaries Models for Three-Dimensional Drawings Three Approaches to 3D-Orthogonal Box-Drawings Approach I: Lifting Edges Approach II: Lifting Half-Edges The Three-Phase Method Conclusion and Open Problems References Using Graph Layout to Visualize Train Interconnection Data Introduction Random Field Models Layout Model Experiments References Difference Metrics for Interactive Orthogonal Graph Drawing Algorithms Introduction Metrics Preliminaries Distance Proximity Orthogonal Ordering Shape Topology Analyzing the Metrics Future Work References Upward Planarity Checking: ``Faces Are More than Polygons'' Introduction Preliminaries Regular Upward Embeddings Regularity Precedence and Dominance Upward Planarity Checking Extensions and Open Problems References A Split&Push Approach to 3D Orthogonal Drawing Introduction A Strategy for Constructing 3D Orthogonal Drawings Feasibility of the Approach The Reduce-Forks Algorithm Experimental Results Conclusions and Open Problems References Geometric Thickness of Complete Graphs Introduction Upper Bounds Lower Bounds The Geometric Thickness of $K_{15}$ Final Remarks References Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs Introduction BSP Tree Based Clustered Graph Drawing The Balanced Aspect Ratio (BAR)Tree Our Results for Cluster-Based Graph Drawing Using a BSP Tree for Cluster Drawing The BAR Tree Constructing the BAR Tree Two-Cut Existence Theorem Using a BAR Tree for Cluster Based Drawing Planar Graphs Extensions Conclusion and Open Problems References On Improving Orthogonal Drawings: The 4M-Algorithm Introduction The Model The 4M-Algorithm Moving Matching Morphing Merging Implementation Issues and Time Complexity Worst Case Analysis Fast and Good Variants of 4M Conclusion References Algorithmic Patterns for Orthogonal Graph Drawing Introduction JDSL Structures Algorithms and Reductions GIOTTO Implementation Design Evaluation and Comparison References A Framework for Drawing Planar Graphs with Curves and Polylines Introduction Related Prior Work Our Results A Framework for Drawing with Curves and Polylines Aesthetic Criteria Complexity Goals Characterizing Our Algorithms in This Framework Our Polyline Drawing Algorithm The Canonical Ordering Our Algorithmic Approach Properties of the Embedding Implementation Details and Running Time Drawing with Curves Comments and Open Problems References Planar Polyline Drawings with Good Angular Resolution Introduction Mathematical Preliminaries The Algorithm Computation of the Ordered Partition Assignment of In- and Outpoints Computation of Coordinates The Analysis The Algorithm in Practice Conclusions References A Layout Adjustment Problem for Disjoint Rectangles Preserving Orthogonal Order Introduction Definition A Layout Adjustment Problem The NP-Completeness of LADR The Transformation of 3-SAT into ILADR Proof A Layout Adjustment Algorithm Push Force-Scan Algorithm The Improvement of PFS The Validity of the Algorithm Conclusion References Drawing Algorithms for Series-Parallel Digraphs in Two and Three Dimensions Introduction Series Parallel Digraphs Symmetric Drawings in Two Dimensions Geometric Automorphisms of Graphs and Symmetries of Graph Drawings Geometric Automorphisms of Series Parallel Digraphs The Two Dimensional Drawing Algorithm Drawing Series Parallel Digraphs in Three Dimensions Conclusion References Approximation Algorithms for Finding Best Viewpoints Introduction Good Viewpoints Bad Viewpoint Arrangements Rotational Separation Diagrams Observed Separation Diagrams Approximate Solutions Iterative Improvement Algorithms Pruning Clipping Force-Directed Algorithms Randomised Force-Direction Experimental Results References Level Planarity Testing in Linear Time Introduction Preliminaries A Correct Linear Time Level Planarity Test Remarks References Crossing Number of Abstract Topological Graphs Drawing Graphs When Only Some Pairs of Egdes Are Allowed to Cross Abstract Topological Graphs and Intersection Graphs Crossing Number of AT-Graphs Is There Always a Single Crossing? Conclusion References Self-Organizing Graphs - A Neural Network Perspective of Graph Layout Introduction Kohonen's Self-Organizing Maps Competitive Learning The Kohonen Network From Self-Organizing Maps to Self-Organizing Graphs The ISOM Layout Algorithm Comparison to Force-Directed Layout Experimental Evaluation Self-Organizing Graphs in 3D and on Spheres Extensions Conclusions References Embedding Planar Graphs at Fixed Vertex Locations Introduction Embedding Algorithm -- Proof of Theorem 1 Lower Bound -- Proof of Theorem 2 Remarks References Proximity Drawings: Three Dimensions Are Better than Two Introduction. Preliminaries. The Algorithm. Phase 1: The Front Drawing. Phase 2: Equally Space the Children. Proof of Correctness. Exponential Area versus Polynomial Volume. Class of Graphs. Linear-Volume Drawings. Proof of Correctness. Open Problems. References NP-Completeness of Some Tree-Clustering Problems Introduction Basic Notions Main Results Tree of Paths Tree of Cycles Conclusion References Refinement of Orthogonal Graph Drawings Introduction Refinement Implementation and Experimental Results Implementation Experimental Results Conclusions and Future Work Acknowledgments References A Combinatorial Framework for Map Labeling Introduction Framework Algorithm Experiments An Algorithm for Three-Dimensional Orthogonal Graph Drawing Introduction Balanced Orderings The `Unique Coordinates' Model The Algorithm Experimental Results Acknowledgements References Graph Multidrawing: Finding Nice Drawings Without Defining Nice Introduction Graph Multidrawing {sc Smile}: A Proof-of-Concept Implementation What {sc smile }Does How {sc smile }Does It Future Directions Layout Dispersion Presentation and Feedback Conclusion References Edge Labeling in the Graph Layout Toolkit Introduction Objectives Interface Algorithms Conclusion References Improved Force-Directed Layouts Introduction Cleaning the Layout Implementation Examples Related Work Conclusions and Future Work References A Fully Animated Interactive System for Clustering and Navigating Huge Graphs Introduction The Framework The Graph Level The Clustering Level The Abridgement Level The Picture Level The Force Model Animations Conclusions References Drawing Large Graphs with H3Viewer and Site Manager Motivation and Context Spanning Trees Abstraction System Interaction Speed and Size Availability Hyperbolic Layout Drawing Adaptive Drawing Drawing Implementation Attributes Conclusion Acknowledgements References Cooperation between Interactive Actions and Automatic Drawing in a Schematic Editor Introduction Quasi-Visibility Drawing of Compound Digraphs Extensions to the S-M Algorithm A Recursive Structure of Recursive Structures Constraints for Satisfactory Single-Line Diagrams Editing with the Automatic Drawing Menu Editing with the Standard Graphic Operations Automatic Bidirectional Drawing Conclusion Future Work References 1. N. De Guise, G. Paris, M. Rochefort, IREQ: Extending a Real-Time Power System Simulator’s Grap... 2. G. Paris: Automatic Drawing of Compound Digraphs for a Real-Time Power System Simulator. Proc.... 3. M. Rochefort, N. De Guise, L. Gingras, IREQ: Development of a graphical user interface for a r... 4. K. Sugiyama, K. Misue: Visualization of Structural Information: Automatic Drawing of Compound ... 5. T. Roxborough, A. Sen: Graph Clustering Using Multiway Ratio Cut. Proc. 5th Symposium on Graph... 6. P. Eades, Q-W Feng, X Lin: Straight-Line Drawing Algorithms for Hierarchical Graphs and Cluste... 7. U. Föbmeier, G. Kant, M. Kaufmann: 2-Visibility Drawings of Planar Graphs. Proc. 5th Symposium... 8. G. Sander: A Fast Heuristic for Hierarchical Manhattan Layout. Proc. 4th Symposium on Graph Dr... Visualization of Parallel Execution Graphs Introduction Timing Parallel Applications in DTS A Graph Theoretical Formulation Algorithms Computing $y$-Coordinates Computing $x$-Coordinates Some Examples Conclusion Reference JIGGLE: Java Interactive Graph Layout Environment Introduction Graph Drawing as Numerical Optimization Our Physically Based Model for Mixed Graphs Computing the Forces Efficiently The Optimization Procedure Empirical Results Examples Future Work References Graph-Drawing Contest Report Introduction Winning Submissions Category A Category B Category C Category D Observations and Conclusions Acknowledgements References Implementation of an Efficient Constraint Solver for the Layout of Graphs in Delaunay References Planar Drawings of Origami Polyhedra References Human Perception of Laid-Out Graphs Ptolomaeus: The Web Cartographer Flexible Graph Layout and Editing for Commercial Applications Introduction Products Graph Layout Toolkit Graph Editor Toolkit Commercial Applications Software Architecture References Multidimensional Outlines - Wordgraphs VISA: A Tool for Visualizing and Animating Automata and Formal Languages References Elastic Labels on the Perimeter of a Rectangle References VGJ: Visualizing Graphs Through Java Introduction Graph Editing Capabilities Layout Algorithms References A Library of Algorithms for Graph Drawing The Size of the Open Sphere of Influence Graph in Metric Spaces Introduction An Upper Bound on the Number of Edges A Lower Bound on the Maximum Number of Edges References Maximum Weight Triangulation and Graph Drawing Introduction Adding Constraints to an Algorithm for Orthogonal Graph Drawing References On Computing and Drawing Maxmin-Height Covering Triangulation Introduction Results References Author Index

this Book Constitutes The Strictly Refereed Post-conference Proceedings Of The 6th International Symposium On Graph Drawing, Gd '98, Held In Montreal, Canada In August 1998.
the 23 Revised Full Papers Presented Were Carefully Selected For Inclusion In The Book From A Total Of 57 Submissions. Also Included Are Nine System Demonstrations And Abstracts Of 14 Selected Posters. The Papers Presented Cover The Whole Range Of Graph Drawing, Ranging From Theoretical Aspects In Graph Theory To Graph Drawing Systems Design And Evaluation, Graph Layout And Diagram Design.

This Book Constitutes The Strictly Refereed Post-conference Proceedings Of The 6th International Symposium On Graph Drawing, Gd '98, Held In Montreal, Canada In August 1998. The 23 Revised Full Papers Presented Were Carefully Selected For Inclusion In The Book From A Total Of 57 Submissions. Also Included Are Nine System Demonstrations And Abstracts Of 14 Selected Posters. The Papers Presented Cover The Whole Range Of Graph Drawing, Ranging From Theoretical Aspects In Graph Theory To Graph Drawing Systems Design And Evaluation, Graph Layout And Diagram Design. This book constitutes the thoroughly refereed post-conference proceedings of the 20th International Symposium on Graph Drawing, GD 2012, held in Redmond, WA, USA, in September 2012.