Graph Drawing

✍ Scribed by Jan Kratochvil (editor)

• Publisher: Springer
• Year: 1999
• Tongue: English
• Leaves: 435
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

Title Page
Preface
Organization
Program Committee
Organizing Committee
Table of Contents
The Anatomy of a Geometric Algorithm?
Turn-Regularity and Planar Orthogonal
Drawings
Introduction
Preliminaries
Basic Definitions
Switch-Regularity
Turn-Regularity and Switch-Regularity
Orthogonal Relations
Turn-Regularity
Turn-Regularity and Switch-Regularity
Orientations and Paths
Turn-Regularity and Orthogonal Relations
Turn-Regularity and Drawing Algorithms
Experiments
Compaction Heuristics
Test Suite and Experimental Results
Conclusions and Future Work
Combining Graph Labeling and Compaction
Introduction
Constraint Graphs
Modeling the Labels
Optimal Graph Labeling
Conclusions and Future Plans
Almost Bend-Optimal Planar Orthogonal
Drawings of Biconnected Degree-3 Planar
Graphs in Quadratic Time
Introduction
Spirality and Polar Drawings
Drawing Triconnected Cubic Plane Graphs with Minimum Bends
SPQR Tree
Main Theorem
Fully Dynamic 3-Dimensional Orthogonal Graph
Drawing
Introduction and Previous Work
Drawing Graphs in $O(n^2)$ Volume with 6 Bends
Introduction and Definitions
Proof of Correctness
Dynamic Case
Variants
Achieving 5 Bends per Edge
Spiral Layout
Self-Loops
Implementation and Experimental Results
Conclusion and Open Problems
Appendix: Routings
An E log E Line Crossing Algorithm for Levelled
Graphs
Introduction
Previous Work
Leveled Graphs and Layout
Leveled Graphs and Intersections
The LevelCross Algorithm
Implementation Results
Conclusions
Level Planar Embedding in Linear Time
Introduction
Preliminaries
Concept of the Algorithm
Augmentation
Remarks
Higres - Visualization System for Clustered
Graphs and Graph Algorithms
Introduction
Clustered Graphs in Higres
Visualization
User Interface
Algorithms Animation
Conclusion
Partitioning Approach to Visualization of Large
Graphs
Approaches to Clustering in Graphs
Cores
Core Decomposition
Clusterings in Graphs
Example -- World Trade Graph
Conclusion
Graph Clustering Using Distance-k Cliques
Software Demonstration
Introduction
Clustering Using Distance-k Cliques
Description of the Algorithms
Analysis of Algorithms
Experimental Results and Discussions
A Framework for Circular Drawings
of Networks
Introduction
Circular Drawings of Biconnected Graphs
Circular Drawings of Nonbiconnected Graphs
Drawings of Nonbiconnected Graphs
Algorithm CIRCULAR - with Radial
Implementation and Experiments
Drawing Planar Graphs with Circular Arcs
Introduction
Prior Related Work
Our Results
Algorithm
Vertex Joint Box
The Invariants
The Shifting Set
The Construction
Drawing with Circular Arcs
Drawing Graphs in the Hyperbolic Plane
Introduction
The Poincar{{accent 19 e}} Half-Plane
The Unit Disk Model of the Hyperbolic Plane
Hyperbolic Primal Dual Circle Packings
Drawing Primitives
Circles
Hyperbolic Line Segments
Drawing in the Hyperbolic Plane
Examples
Graph Planarity and Related Topics
Basics
Testing Planarity in Linear Time
Schnyder's Theorem and Drawing on a Grid
Colin de Verdiere's Parameter
Separators
The Two Paths Problem
Pfaffian Orientations
Linkless Embeddings
A Digression
The Four-Color Theorem
Outline of a Proof of the 4CT
Grid Drawings of Four-Connected Plane Graphs
Introduction
Main Theorem
Drawing G'
Graph Embedding with Topological
Cycle-Constraints
Introduction
Preliminaries
Cycle-Constraints
Restricted Cycle-Constraints
Decomposition Trees
Embedding Algorithm
Embedding Vertices at Points:
Few Bends Suffice for Planar Graphs
Introduction
A Basic Technique
The General Case
The Lower Bound
The NP-Completeness Result
Discussion
The Constrained Crossing Minimization
Problem
Introduction
Constrained Crossing Minimization and Shortest Crossing Walks
An ILP for Trails
An ILP for the Shortest Crossing Trails Problem
The Shortest Crossing Walks Problem
Computational Experiments and Results
Planarity-Preserving Clustering and Embedding
for Large Planar Graphs
Introduction
Prior Related Work on Clustered Graph Drawing
Our Results
Hierarchical Embedding of Planar Graphs
Edge Contraction and Separating Triangles
Simple Matching in Maximally Planar Graphs
Algorithm and Analysis
Constructing the Embedding
An Algorithm for Drawing Compound Graphs
Introduction
Definitions
Algorithm for Drawing Compound Graphs
Description of the NUAGE Algorithm
Step 1: Construction of a Nested Graph Associated with a Compound Graph
Step 2: Drawing of the Nested Graph
Refinement Technique
The Vertex-Exchange Graph: A New Concept
for Multi-level Crossing Minimisation
Introduction
The Vertex-Exchange Graph
Definition and Properties
Odd-Labelled Cycles
Level Planarity Testing by the Vertex-Exchange Graph
Layout Calculation of a Level Planar Graph
Crossing Minimisation
Crossing Number Bounds
Conclusions
Using Sifting for k-Layer Straightline Crossing
Minimization
Introduction
Algorithms Known from the Literature
Sifting for One Sided Crossing Minimization
Extending Sifting to k-Layered Directed Graphs
Conclusions
On 3-Layer Crossings and Pseudo Arrangements
Introduction
Basic Concepts and Notations
Arrangements and 3-Layer Drawings
Visualizing Algorithms for the Design and Analysis of
Survivable Networks
1 Introduction
2 Inside Drawing
3 Outside Drawing
4 Mixed Drawing
4.1 Basic idea
4.2 Algorithm
5 Conclusion and Open Problems
6 Acknowledgement
References
LayoutShow: A Signed Applet/Application for
Graph Drawing and Experimentation
Introduction
Features
Outline
The LayoutShow Applet
The Overall Design of the System
Bugs and Limitations
Centrality in Policy Network Drawings
Introduction
Policy Networks and Centrality
Centrality Drawings
Analyzing Local Drug Policies
Straight-Line Drawings of Protein Interactions
Introduction
Biological Context
Large Straight-Line Drawings
Evaluation
Further Work
Conclusions
Acknowledgements
Art of Drawing
Introduction
Drawing and Sketching
The Basic Scheme
Defining Sketches
Nature of Sketches
Eternal Style and Quality
Rarity and Inaccessibility
Summary (Of the First Part of the Lecture)
Appendix
An Heuristic for Graph Symmetry Detection
Introduction
Automorphisms and Symmetries
The Embedding Model
Euclidean Semi-Distances
Defining a Semi-Distance in a Graph
Embedding and Projecting the Graph on Planes
The Heuristic by Examples
All the Eigenvalues are Distinct
The First Eigenvalue has Multiplicity Two
General Case
More Pictures
Open Questions
Concluding Remarks
Isomorphic Subgraphs
Introduction
Basic Notions
NP-Completeness of IES and INS
Outerplanar Graphs
Planar Graphs
Isomorphic Subtrees
Open Questions and Outlook
Orthogonal and Quasi-upward Drawings
with Vertices of Prescribed Size
Introduction
Preliminaries and Drawing Conventions
Computing Podavsnef Drawings
Experiments with GDToolkit
Computing Pqudavs Drawings
Multi-dimensional Orthogonal Graph Drawing
with Small Boxes
Introduction
The General Position Model
Determining Vertex Size
Port Assignment
Balanced Graph Layout
Layout-Based Algorithms
Routing-Based Algorithms
Geometric Realization of Simplicial Complexes
Introduction
The Complex of a $d$-Representation
Geometric Realizations of Simplicial Complexes
Geometric Realization of a $d$-Representation
Triangulation
Shellability of Standard Complexes
Visibility Representations of Complete Graphs
Introduction
General properties
Triangles
Open problems
Triangle-Free Planar Graphs as Segments
Intersection Graphs
Introduction
Convex Faces with Three Directions
Triangle-Free Graphs
Concluding Remarks
A Force-Directed Algorithm that Preserves Edge
Crossing Properties
Introduction
PrEd algorithm
Computation of forces
Computation of the amplitude of moves
Correctness
Further work
Conclusion
Rectangle of Influence Drawings of Graphs
without Filled 3-Cycles
Introduction
Definitions
Rectangle of Influence Drawings for NF3-Graphs
Biconnected, Chordless, Internally Triangulated {{NF3-graphs} }
Extension to all NF3-Graphs
Conclusion
Voronoi Drawings of Trees?
Introduction
Preliminaries
Euclidean Voronoi Drawings of Trees
Point Sets in the Manhattan Metric
Manhattan Voronoi Drawings of Trees
Infinite Trees and the Future
Introduction
The Framework and the Drawing Strategies
Experimental Results
Analysis
Analysis of Leftmost-Embedding Algorithm
Analysis of Central-Embedding Algorithm
Latour - A Tree Visualisation System
Introduction
Graph/Tree Layout
Hierarchical View
Radial View
Balloon View
Interaction and Navigation
Zoom, Pan, Fish--Eye
Complexity Visual Cues
Animation
Beyond Trees
Packed Forests
Dag's
Conclusions
Graph-Drawing Contest Report
Introduction
Winning Submissions
Category A
Category B
Category C
Category D
Observations and Conclusions
Hunting Down Graph B
Orthogonal and Straight-Line Drawings of
Graphs with Succinct Representations
Electronic Biochemical Pathways*
Author Index