Handbook of Graph Drawing and Visualization: Draft of 2013 edition

Cover
Preface
About the Editor
Contents
1 Planarity Testing and Embedding
1.1 Introduction
1.2 Properties and Characterizations of Planar Graphs
1.2.1 Basic Definitions
1.2.2 Properties
1.2.3 Characterizations
1.3 Planarity Problems
1.3.1 Constrained Planarity
1.3.2 Deletion and Partition Problems
1.3.3 Upward Planarity
1.3.4 Outerplanarity
1.4 History of Planarity Algorithms
1.5 Common Algorithmic Techniques and Tools
1.6 Cycle-Based Algorithms
1.6.1 Adding Segments: The Auslander-Parter Algorithm
1.6.2 Adding Paths: The Hopcroft-Tarjan Algorithm
1.6.3 Adding Edges: The de Fraysseix-Ossona de Mendez-Rosenstiehl Algorithm
1.7 Vertex Addition Algorithms
1.7.1 The Lempel-Even-Cederbaum Algorithm
1.7.2 The Shih-Hsu Algorithm
1.7.3 The Boyer-Myrvold Algorithm
1.8 Frontiers in Planarity
1.8.1 Simultaneous Planarity
1.8.2 Clustered Planarity
1.8.3 Decomposition-Based Planarity
2 Crossings and Planarization
2.1 Introduction
2.2 Crossing Numbers
2.2.1 Known Bounds
2.3 Complexity of Crossing Minimization
2.3.1 NP-hardness
2.3.2 Fixed Parameter Tractability
2.4 Exact Crossing Minimization
2.4.1 Subdivision-Based Formulation
2.4.2 Ordering-Based Formulation
2.4.3 Branch-and-Cut-and-Prize
2.5 The Planarization Method
2.5.1 Overview
2.5.2 Planar Subgraphs
2.5.3 Edge Insertion
2.5.4 Experimental Results
2.5.5 Beyond Edge Insertion
2.6 Approximation Algorithms
3 Symmetric Graph Drawing
3.1 Introduction
3.2 Basic Concepts for Symmetric Graph Drawing
3.2.1 Drawing of a graph
3.2.2 Automorphisms of a graph
3.2.3 Symmetries of a graph drawing
3.3 Characterization of Geometric Automorphism Groups
3.4 Finding Geometric Automorphisms
3.5 Symmetric Drawings of Planar Graphs
3.5.1 Triconnected planar graphs
3.5.2 Biconnected planar graphs
3.5.3 One-connected planar graphs
3.5.4 Disconnected planar graphs
3.5.5 Drawing algorithms
3.6 Conclusion
3.6.1 Further topics
3.6.2 Open problems
4 Proximity Drawings
4.1 Introduction
4.2 Proximity Rules and Proximity Drawings
4.2.1 Proximity Region Based Drawings
4.2.2 Global Proximity
4.3 Results
4.3.1 Minimum Weight Drawings
4.3.2 Delaunay and Voronoi Drawings
4.3.3 Rectangle of In uence Drawings
4.3.4 Nearest Neighbor Drawings
4.3.5 Sphere of In uence Drawings
4.3.6 -Drawings
4.4 Variations of Proximity Drawings
4.4.1 Witness Proximity Drawings
4.4.2 Weak Proximity Drawings
4.4.3 Approximate Proximity Drawings
4.5 Open Problems
4.6 Beyond this Chapter
5 Tree Drawing Algorithms
5.1 Introduction
5.1.1 Drawing Conventions
5.1.2 Aesthetics
5.2 Level-Based Approach
5.3 H-V Approach
5.4 Path-Based Approach
5.5 Ringed Circular Layout Approach
5.6 Separation-Based Approach
5.7 Algorithms for Drawing Binary Trees
5.7.1 Theoretical Results
5.7.2 Experimental Analysis
5.7.3 Unordered Trees
5.7.4 Ordered Trees
5.8 Algorithms for Drawing General Trees
5.8.1 Theoretical Results
5.8.2 Unordered Trees
5.8.3 Ordered Trees
5.9 Other Tree Drawing Methods
6 Planar Straight-Line Drawing Algorithms
6.1 Introduction
6.2 Preliminaries
6.2.1 Planar Drawings
6.2.2 Convex Drawings
6.2.3 Connectivity
6.3 Real-Coordinate Drawings
6.4 Grid Drawings
6.5 Canonical Orderings
6.6 Shift Method
6.6.1 Construction
6.6.2 Implementation
6.6.3 Refinements and Variations
6.7 Realizer Method
6.7.1 Realizers
6.7.2 Barycentric Representation
6.7.3 Implementation
6.7.4 Refinements and Variations
7 Planar Orthogonal and Polyline Drawing Algorithms
7.1 Introduction
7.2 Preliminaries
7.2.1 Definitions
7.2.2 Canonical Ordering and Shifting Sets
7.2.3 Visibility Representations
7.2.4 Network Flows
7.3 Orthogonal Drawings
7.3.1 Orthogonal Drawings from Visibility Representations
7.3.2 Network Flow Algorithms
7.4 Polyline Drawings
7.4.1 Mixed-Model Algorithm
7.4.2 One Bend Algorithm
7.4.3 Vertex Regions
7.4.4 The Embedding
7.5 Conclusion
8 Spine and Radial Drawings
8.1 Introduction
8.2 A Unified Framework for Spine and Radial Drawings
8.2.1 Definitions
8.2.2 Scenarios
8.3 Results in the General Scenario
8.3.1 Spine Drawings in the General Scenario
8.3.2 Radial Drawings in the General Scenario
8.4 Results in the Constrained Scenarios
8.4.1 Upright and Proper Spine Drawings
8.4.2 Partitioned Spine Drawings
8.4.3 Radial Drawings with Assigned Layers
8.5 Related Problems
8.5.1 Hamiltonicity
8.5.2 Point-Set Embeddability
8.6 Conclusions
9 Circular Drawing Algorithms
9.1 Introduction
9.1.1 Other Circular Drawing Techniques
9.1.2 Complexity of the Circular Graph Drawing Problem
9.2 Circular Drawings of Biconnected Graphs
9.2.1 Properties of Algorithm CIRCULAR
9.3 Further Reduction of Edge Crossings
9.3.1 Counting All the Crossings in a Circular Drawing
9.3.2 Determining the New Number of Crossings after Moving a Node
9.4 Nonbiconnected Graphs on a Single Circle
9.5 Nonbiconnected Graphs on Multiple Circles
9.6 A Framework for User-Grouped Circular Drawing
9.6.1 Circular-Track Force-Directed
9.6.2 A Technique for Creating User-Grouped Circular Drawings
9.7 Implementation and Experiments
9.7.1 Experimental Analysis of Algorithm CIRCULAR
9.7.2 Implementation Issues
9.7.3 Experimental Analysis of Algorithm CIRCULAR-with Radial
9.7.4 Implementation of Algorithm CIRCULAR-with Forces
9.8 Conclusions
10 Rectangular Drawing Algorithms
10.1 Introduction
10.2 Rectangular Drawing and Matching
10.3 Linear Algorithms for Rectangular Drawing
10.3.1 Thomassen's Theorem
10.3.2 Drawing Algorithms
10.3.3 Drawing without Designated Corners
10.4 Box-Rectangular Drawing
10.5 Conclusions
11 Simultaneous Embedding of Planar Graphs
11.1 Introduction
11.1.1 Problem Definitions
11.1.2 Overview and Outline
11.2 Simultaneous Geometric Embedding
11.2.1 Graph Classes with SGE
11.2.2 Examples without SGE
11.2.3 Related Work
11.3 Simultaneous Embedding with Fixed Edges
11.3.1 Positive and Negative Examples
11.3.2 Testing SEFE
11.3.3 Related Work
11.4 Simultaneous Embedding
11.5 Colored Simultaneous Embedding
11.6 Matched Drawings
11.7 Other Simultaneous Representations
11.7.1 A Plane Graph and Its Dual
11.7.2 Intersection Representations
11.8 Practical Approaches to Dynamic Graph Drawing
11.9 Morphing Planar Drawings
11.10 Open Problems
12 Force-Directed Drawing Algorithms
12.1 Introduction
12.2 Spring Systems and Electrical Forces
12.3 The Barycentric Method
12.4 Graph Theoretic Distances Approach
12.5 Further Spring Refinements
12.6 Large Graphs
12.7 Stress Majorization
12.8 Non-Euclidean Approaches
12.9 Lombardi Spring Embedders
12.10 Dynamic Graph Drawing
12.11 Conclusion
13 Hierarchical Drawing Algorithms
13.1 Introduction
13.1.1 Current Approaches and Their Limitations
13.1.2 Overview of Sugiyama's Framework
13.2 Cycle Removal
13.2.1 Heuristics Based on Vertex Orderings
13.2.2 Berger-Shor Algorithm
13.2.3 Greedy Cycle Removal
13.2.4 Heuristics Based on Cycle Breaking
13.2.5 Minimum FAS in a Weighted Digraph
13.2.6 Other Approaches
13.3 Layer Assignment
13.3.1 Additional Criteria and Variations of the Problem
13.3.2 Layer Assignment Algorithms
13.3.3 The Layering Algorithms Compared
13.3.4 Layer-Assignment with Long Vertices
13.4 Edge Concentration
13.4.1 Intersection Cover
13.4.2 Newbery's Algorithm
13.5 Vertex Ordering
13.5.1 One-Sided Crossing Minimization
13.5.2 Multi-Layer Crossing Minimization
13.5.3 Planarization { An Alternative
13.6 x-Coordinate Assignment
13.7 Extensions and Alternatives to Sugiyama's Framework
14 Three-Dimensional Drawings
14.1 Introduction
14.2 Straight-Line and Polyline Grid Drawings
14.2.1 Straight-Line Grid Drawings
14.2.2 Upward
14.2.3 Polyline
14.3 Orthogonal Grid Drawings
14.3.1 Point-Drawings
14.3.2 Box-Drawings
14.4 Thickness
14.5 Other (Non-Grid) 3D Drawing Conventions
15 Labeling Algorithms
15.1 Introduction
15.2 The Labeling Problem
15.2.1 Searching for a Good Label Assignment
15.2.2 A Definition of the Labeling Problem
15.3 Solving the Labeling Problem
15.3.1 The GFLP Problem
15.3.2 The ELP Problem
15.3.3 The NLP Problem
15.3.4 The MLP Problem
15.3.5 Placing Labels by Modifying the Drawing
16 Graph Markup Language (GraphML)
16.1 Introduction
16.1.1 Related Formats
16.2 Basic Concepts
16.2.1 Header
16.2.2 Topology
16.2.3 Attributes
16.2.4 Parseinfo
16.3 Advanced Concepts
16.3.1 Nested Graphs
16.3.2 Hypergraphs
16.3.3 Ports
16.4 Extending GraphML
16.4.1 Adding XML-Attributes
16.4.2 Adding Structured Content
16.5 Transforming GraphML
16.5.1 Means of Transformation
16.5.2 Transformation Types
16.5.3 Language Binding
16.6 Using GraphML
17 The Open Graph Drawing Framework (OGDF)
17.1 Introduction
17.1.1 The History of the OGDF
17.1.2 Outline
17.2 Major Design Concepts
17.2.1 Modularization
17.2.2 Self-Contained and Portable Source Code
17.3 General Algorithms and Data Structures
17.3.1 Augmentation and Subgraph Algorithms
17.3.2 Graph Decomposition
17.3.3 Planarity and Planarization
17.4 Graph Drawing Algorithms
17.4.1 Planar Drawing Algorithms
17.4.2 Hierarchical Drawing Algorithms
17.4.3 Energy-Based Drawing Algorithms
17.4.4 Drawing Clustered Graphs
17.5 Success Stories
17.5.1 SPQR-Trees
17.5.2 Exact Crossing Minimization
17.5.3 Upward Graph Drawing
18 GDToolkit
18.1 Introduction
18.2 Key Features of GDToolkit
18.3 Graph-classes and their Hierarchy
18.3.1 Topology level
18.3.2 Shape Level
18.3.3 Metrics Level
18.4 Constructors
18.5 Management of Constraints
18.5.1 Topology Constraints
18.5.2 Shape Constraints
18.5.3 Metrics Constraints
18.6 Examples of Applications
18.6.1 Internet Analysis
18.6.2 Web Searching
18.6.3 Database Analysis
19 PIGALE
19.1 Introduction
19.1.1 Why GPL?
19.1.2 Chapter Organization
19.2 Data Structures
19.2.1 The Topological Quasi-Static Model
19.2.2 Graph Properties
19.3 Basic Graph Algorithms
19.3.1 Depth-First Search
19.3.2 Planarity and Nonplanar Subgraph Exhibition
19.3.3 Connectivity Tests
19.3.4 Augmentation of Planar Graphs
19.3.5 Graph Symmetry and Clustering
19.4 Random Map Generators
19.5 Graph Drawing Algorithms
19.5.1 Planar Straight-Line Grid Drawings
19.5.2 Spring Embedders
19.5.3 Visibility Drawing and Variants
19.5.4 Contact Drawings
19.5.5 Spectral Drawings in IRn
19.6 Implementation
19.6.1 User Interface
19.6.2 File Storage
19.6.3 Macro Recording
19.6.4 Multi-Threaded Server
19.7 Interfacing with PIGALE
20 Biological Networks
20.1 Introduction
20.1.1 Molecular Biological Foundations
20.1.2 Biological Networks
20.2 Signal Transduction and Gene Regulatory Networks
20.2.1 Definition
20.2.2 Visualization Requirements
20.2.3 Layout Methods
20.3 Protein-Protein Interaction Networks
20.3.1 Definition
20.3.2 Visualization Requirements
20.3.3 Layout Methods
20.4 Metabolic Networks
20.4.1 Definition
20.4.2 Visualization Requirements
20.4.3 Layout Methods
20.5 Phylogenetic Trees
20.5.1 Definition
20.5.2 Visualization Requirements
20.5.3 Layout Methods
20.6 Discussion
21 Computer Security
21.1 Introduction
21.1.1 Motivation
21.1.2 Chapter Organization
21.2 Network Monitoring
21.2.1 Intrusion Detection
21.2.2 Traffic Analysis
21.2.3 Internal vs. External Hosts
21.2.4 Similarity Analysis for Traffic Logs and Scans
21.2.5 Visualization of Address Space
21.2.6 Visualization of Name Server Migration
21.3 Border Gateway Protocol
21.3.1 Topology of Autonomous Systems
21.3.2 BGP Monitoring
21.3.3 BGP Evolution
21.4 Access Control
21.4.1 Rule-Based Access Control
21.4.2 File System Access-Control
21.4.3 Trust Negotiation
21.4.4 Privacy Settings in Social Networks
21.5 Attack Graphs
21.5.1 Model
21.5.2 Tools
21.6 Private Graph Drawing
21.6.1 Compressed Scanning
21.6.2 Data-Oblivious Drawing Algorithms
22 Graph Drawing for Data Analytics
22.1 Introduction
22.2 Where Network Visualization Creates High Value
22.2.1 User Interface
22.2.2 Visual Presentation and Branding
22.2.3 Executive Dashboards
22.2.4 Real-Time Visual Reports
22.2.5 Visual Discovery for Deep Analysis
22.2.6 Searching and Exploration
22.2.7 Domain Task-Speci c Visualizations
22.3 Network Visualization Sweet Spot
22.4 Customers for Network Visualization Software
22.5 Business Models for Network Visualization
22.5.1 Custom Software
22.5.2 Enterprise Software
22.5.3 Shrink-Wrapped Software
22.5.4 Open Source Software
22.5.5 Cloud Computing
22.5.6 Network Visualization Deployments
22.6 Thin-client Network Visualization
22.7 Discussion and Summary
23 Graph Drawing and Cartography
23.1 Introduction
23.2 Paths
23.2.1 Simplifying and Schematizing Polygonal Paths
23.2.2 Continuous Generalization for Polygonal Lines
23.3 Matchings
23.3.1 Boundary Labeling with Type-s Leaders
23.3.2 Boundary Labeling with Type-po Leaders
23.4 Trees
23.5 Plane and Near-Plane Graphs
23.5.1 Schematic Road Maps
23.5.2 Metro Maps
23.5.3 Street Maps with Focus Regions
23.5.4 Cable Plans
23.6 Other Graphs
23.6.1 Timetable Graphs
23.6.2 Internet Traffic
23.6.3 Social Networks
24 Graph Drawing in Education
24.1 Introduction
24.2 Applications
24.2.1 Algorithm Animation
24.2.2 Algorithm Simulation
24.2.3 Exercise Systems
24.2.4 Exploration Systems
24.2.5 Program Visualization
24.2.6 Software Visualization
24.3 Graph Drawing for Algorithm Animation
24.3.1 A Unified Approach to Drawing Data Structures
24.3.2 Special-Purpose Layouts
24.4 Graph Drawing for Program Visualization
24.4.1 Complex Node Structures
24.4.2 Taking Structure into Account
24.4.3 Drawing Execution Environments
24.4.4 Drawing Sequence Diagrams
24.5 Graph Drawing for Software Visualization
24.5.1 Drawing UML Class Diagrams
24.6 Sequences of Drawings
24.6.1 Trees
24.6.2 Force-Directed Layout
24.6.3 Sugiyama-Style Hierarchical Layout
24.6.4 Offline Dynamic Graph Drawing
24.6.5 Smooth Animation
25 Computer Networks
25.1 Introduction
25.1.1 Benefits of Visualizing Computer Networks
25.2 The Very Basics of Computer Networking
25.2.1 A Network Model
25.2.2 Interconnection Technologies
25.2.3 Routing and Routing Protocols
25.2.4 The Internet Structure
25.2.5 The User's Point of View
25.3 A Taxonomy of Visualization Methods and Tools
25.3.1 Visualized Data
25.3.2 Graph Drawing Conventions and Methodologies
25.3.3 Visualization Tools
25.4 Data Sources
25.5 Visualization of the Internet
25.6 Visualization of an Internet Service Provider Network
25.7 Visualization of Local Networks
25.8 Visualization of Basic Internet Services and Speci c Network Contexts
26 Social Networks
26.1 Social Network Analysis
26.2 Visualization Principles
26.2.1 Illustrative Example
26.2.2 Substance, Design, Algorithm
26.3 Substance-Based Designs
26.3.1 Prominence
26.3.2 Cohesion
26.3.3 Two-Mode Networks
26.3.4 Dynamics
26.4 Trends and Challenges
Index