Graph Drawing

Name: Graph Drawing | 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010. Revised Selected Papers
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010. Revised Selected Papers

Ulrik Brandes Sabine Cornelsen(Herausgeber*in)

Springer (Verlag)

Erschienen am 10. Februar 2011

XIV, 414 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-18469-7 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Title Page
Preface
Organization
Table of Contents
Papers
On the Size of Graphs That Admit Polyline Drawings with Few Bends and Crossing Angles
Introduction
Preliminaries
Polyline Drawing with the Same Crossing Angle
Crossings between End Segments
Crossings between End Segments and Middle Segments
Proofs of Theorems 1 and 3
Proof of Theorem 4
References
Monotone Drawings of Graphs
Introduction
Definitions and Preliminaries
Properties of Monotone Drawings
Monotone Drawings of Trees
Planar Monotone Drawings of Biconnected Graphs
Conclusions and Open Problems
References
Upward Geometric Graph Embeddings into Point Sets
Introduction
Preliminaries
Embeddings of Directed Graphs into Point Sets
Embeddings of Directed Caterpillars into Convex Point Sets
Embeddings of Directed Paths into General Point Sets
Open Problems
References
On a Tree and a Path with No Geometric Simultaneous Embedding
Introduction
Preliminaries
The Counterexample
Overview
Constructing a Gse of a Tree of Height 2 and a Path
Conclusions
References
Difference Map Readability for Dynamic Graphs
Introduction
Previous and Related Work
Difference Maps
Dynamic Graph Drawing and the Mental Map
Animation vs. Small Multiples for Dynamic Data
The Experiment
Interfaces
Difference Map Encoding
Data Sets
Tasks
Experimental Design
Results
WD vs. ND
WD vs. ND Divided by Interface
Preference Data
Discussion
Does the Difference Map Help?
Does It Help for All Interfaces?
Limitations
Conclusions and Future Work
References
Maximizing the Total Resolution of Graphs
Introduction
Drawings with Optimal Total Resolution for Complete and Complete Bipartite Graphs
A Force Directed Algorithm
Conclusions
References
Plane Drawings of Queue and Deque Graphs
Introduction
Preliminaries
Linear Cylindric Drawings of Deque Graphs
Linear Cylindric Drawings
Characterization of Deque Graphs
Linear Cylindric Drawings of Queue and Mixed Layouts
Queue Graphs
Linear Cylindric Drawings of Mixed Layouts
Conclusion and Future Work
References
An Experimental Evaluation of Multilevel Layout Methods
Introduction
The Multilevel Paradigm
Experimental Study
Implementations
Computational Results
Conclusions
References
Orthogonal Graph Drawing with Flexibility Constraints
Introduction
Preliminaries
The Maximum Rotation with a Fixed Embedding
Biconnected Graphs
Connected Graphs
References
Drawing Ordered ($k$ - 1)-Ary Trees on $k$-Grids
Introduction
Preliminaries
NP-Hardness Results
$O$-Drawings
$OL$-Drawings
$OP$- and $OLP$-Drawings
Heuristic
Contract Edges
Merge Contours
Time Complexity
Conclusion
References
Optimizing Regular Edge Labelings
Introduction
Useful Facts and Reverse Search
Counting Regular Edge Labelings
Upper Bound
Lower Bound
Optimizing RELs for Rectangular Cartograms
References
Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area
Introduction
Preliminaries
Drawing a Graph with a Given Boundary
Application to Drawing Graphs of Genus g
Conclusion and Open Problems
References
Crossing Minimization and Layouts of Directed Hypergraphs with Port Constraints
Introduction
Hypergraphs
Port Constraints
Upward-Planarization
Preprocessing
Feasible Upward-Planar Subgraph
Arc Insertion
Layout
Conclusion
References
Drawing Graphs on a Smartphone
Introduction
A Visualization and Interaction Paradigm
Choosing the Lobe Order
Algorithmic Framework
Experimental Analysis of the Algorithms
Implementation and Case Studies
References
Topology-Driven Force-Directed Algorithms
Introduction and Overview
Related Work
The Topology-Driven Force-Directed Approach
Experimental Study
Conclusions and Open Problems
References
On Graphs Supported by Line Sets
Introduction
Preliminaries
Graphs Supported by Arrangements of Lines
Non-supporting Line Sets
Conclusion and Open Problems
References
Drawing Trees with Perfect Angular Resolution and Polynomial Area
Introduction
Straight-Line Drawings for Unordered Trees
Straight-Line Drawings for Ordered Trees
Lombardi Drawings for Ordered Trees
Drawing Heavy Paths
Drawing Light Children
Conclusion and Closing Remarks
References
Lombardi Drawings of Graphs
Introduction
Circular Lombardi Drawings of Regular Graphs
Two-Degenerate and Three-Degenerate Graphs
2-Degenerate Graphs
3-Degenerate Graphs
Non-crossing Lombardi Drawings
Planar Graphs without Planar Lombardi Drawings
Halin Graphs
Other Classes of Planar Graphs
The Lombardi Spirograph
Conclusions
References
Optimal 3D Angular Resolution for Low-Degree Graphs
Introduction
Three-Bend Drawings of Degree-Four Graphs on a Grid
Two-Bend Drawings of Degree-Three Graphs
Conclusions
References
Improved Lower Bounds on the Area Requirements of Series-Parallel Graphs
Introduction
Preliminaries
Proof of Theorem 2
Conclusions and Open Problems
References
A Computational Approach to Conway's Thrackle Conjecture
Introduction
Conway's Doubling and Preliminaries
Proof of Theorem 1
A Better Upper Bound
Concluding Remarks
References
Optimal $k$-Level Planarization and Crossing Minimization
Introduction
Model
Additional Constraints
Cycle Parity
Leaves
Experimental Results
Conclusion
References
On Touching Triangle Graphs
Introduction
Related Work
Outerplanar Graphs
Algorithm Overview
Grid Graphs
Algorithm Overview
Triangulations
Necessary Conditions
Conclusion and Future Work
References
Triangle Contact Representations and Duality
Introduction
Tools
Stretchability
Schnyder Woods
Mixing Tools
One-to-One Correspondence
Internally 3-Connected Planar Maps
Particular Types of Triangles
References
On Maximum Differential Graph Coloring
Introduction
Related Work
Maximum Differential Coloring and Hamiltonian Path
Algorithms for Maximum Differential Coloring
Differential Chromatic Numbers of Special Graphs
Conclusion
References
Dot Product Representations of Planar Graphs
Introduction and Statement of Results
Preliminaries
Planar Graphs That Are Not 3-Dot Product Graphs
All Planar Graphs Are 4-Dot Product Graphs
References
Drawing Planar Graphs of Bounded Degree with Few Slopes
Introduction
Straight-Line Drawings-Proof of Theorem 1
Two Bends per Edge-Proof of Theorem 3
Lower Bounds
References
Complexity of Finding Non-Planar Rectilinear Drawings of Graphs
Introduction
Existence of Rectilinear Drawings
Rectilinear Drawings of HV-Restricted Graphs
Rectilinear Drawings of Cyclic-Restricted Graphs
Rectilinear Drawings of LRDU-Restricted Graphs
Fixed-Parameter Algorithms
Area-Minimization Drawings
Rectilinear Drawings of LRDU-Restricted Graphs
Conclusions
References
Point-Set Embeddings of Plane 3-Trees
Confluent Drawing Algorithms Using Rectangular Dualization
Introduction
Background and Related Work
Rectangular Dualization
Enforcing the Admissibility Conditions
From Rectangular Dual to Confluent Drawing
Baseline Approach
Improved Approach
Implementation and Results
Confluent Rectangular Drawing for Clustered Graphs
Conclusions
References
Introduction
Preliminaries
Point-Set Embeddings of Plane 3-Trees
Lower Bound
Generalized Case
Conclusion
References
Improving Layered Graph Layouts with Edge Bundling
Introduction
Related Work
Edge Bundling
Identifying Edge Bundles
Straightening Edges
Metro-Map Widening
Experiments
Conclusion, Discussion and Future Work
References
How to Draw a Tait-Colorable Graph
Introduction
Theory of Tait-Colored Graphs
Projective Drawings
The Combinatorial Direction
The Constructibility Direction
Subsequent Results
Quasi-Faithful Drawings
Forced Triples
Realization Spaces
Conclusion
Higher Degree
Ghost Symmetry in the Plane
References
Universal Pointsets for 2-Coloured Trees
Introduction
Properly 2-Coloured Trees
Almost Mono-Chromatic Rooted Trees
Coloured Simultaneous Geometric Embeddings
Open Problems
References
The Quality Ratio of RAC Drawings and Planar Drawings of Planar Graphs
Introduction
Ratio of Area Requirement
Ratio of Edge-Length Ratio
Ratio of Angular Resolution
Conclusions and Further Research
References
Convex Polygon Intersection Graphs
Introduction
P-intersection Graphs
Open Versus Closed Objects
Representing P-intersection Graphs
Helpful Inequalities
Assembling the Model
Solving the Model
Applications
References
Posters
GraphML-Based Exploration and Evaluation of Efficient Parallelization Alternatives for Automation Firmware
Motivation
The EEEPA Tool
Reference
Automatic Generation of Route Sketches
Introduction
Model
Evaluation
References
Visualizing Differences between Two Large Graphs
Introduction
Our Method
Implementation and Results
References
Placing Edge Labels by Modifying an Orthogonal Graph Drawing
Introduction
Solving the OSLP Problem
References
Large Crossing Angles in Circular Layouts
Introduction
Algorithm
Experiments
Conclusion
References
GVSR: An On-Line Guide for Choosing a Graph Visualization Software
Introduction
How to Use the Site?
Future Works
IBM ILOG Multi-platform Graph Layout Technology
Comparative Visualization of User Flows in Voice Portals
Introduction
Comparing User Flows
References
Graph Drawing Contest
Graph Drawing Contest Report
Introduction
Edge Routing - Circuit Diagram
Edge Routing - Author Collaboration Graph
Mystery Graph
Online Challenge
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken