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