Handbook of Graph Drawing and Visualization: Draft of 2013 edition

CRC Press, 2014. — 860 p. Get an In-Depth Understanding of Graph Drawing Techniques, Algorithms, Software, and Applications The Handbook of Graph Drawing and Visualization provides a broad, up-to-date survey of the field of graph drawing. It covers topological and geometric foundations, algorithms, software systems, and visualization applications in business, education, science, and engineering. Each chapter is self-contained and includes extensive references. The first several chapters of the book deal with fundamental topological and geometric concepts and techniques used in graph drawing, such as planarity testing and embedding, crossings and planarization, symmetric drawings, and proximity drawings. The following chapters present a large collection of algorithms for constructing drawings of graphs, including tree, planar straight-line, planar orthogonal and polyline, spine and radial, circular, rectangular, hierarchical, and three-dimensional drawings as well as labeling algorithms, simultaneous embeddings, and force-directed methods. The book then introduces the GraphML language for representing graphs and their drawings and describes three software systems for constructing drawings of graphs: OGDF, GDToolkit, and PIGALE. The final chapters illustrate the use of graph drawing methods in visualization applications for biological networks, computer security, data analytics, education, computer networks, and social networks. Edited by a pioneer in graph drawing and with contributions from leaders in the graph drawing research community, this handbook shows how graph drawing and visualization can be applied in the physical, life, and social sciences. Whether you are a mathematics researcher, IT practitioner, or software developer, the book will help you understand graph drawing methods and graph visualization systems, use graph drawing techniques in your research, and incorporate graph drawing solutions in your products. 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