Graph Drawing

Name: Graph Drawing | 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21-23, 2011, Revised Selected Papers
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21-23, 2011, Revised Selected Papers

Marc van Kreveld Bettina Speckmann(Herausgeber*in)

Springer (Verlag)

Erschienen am 16. Dezember 2011

XIV, 458 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-25878-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
Obituary
Kozo Sugiyama 1945 - 2011
Papers
Confluent Hasse Diagrams
Introduction
Preliminaries
Posets and Lattices
Hasse Diagrams and Upward Planarity
Lattice Completion of a Poset
Confluent Drawing
The Algorithm
Algorithm Correctness and Minimality
Confluent Drawings of Series-Parallel Posets
Conclusions
References
Planar Open Rectangle-of-Influence Drawings with Non-aligned Frames
Background
Preliminaries
Results
Conclusion
References
Proportional Contact Representations of Planar Graphs
Introduction
Related Work
Our Results
Preliminaries
Proportional Point-Contact Representations of Planar Graphs
Subclasses of Planar Graphs with Convex-Shape Representations
2-Segment Graphs and Partial 2-Trees
Maximal Outerplanar Graphs
Conclusion and Open Problems
References
Embedding Plane 3-Trees in R2 and R3
Introduction
Preliminaries
Point-Set Embeddings of Plane 3-Trees in R2
Tetrahedral Embeddings of Tetrahedral 4-Trees
Point-Set Embeddings of Plane 3-Trees in R3
Conclusion
References
Orthogeodesic Point-Set Embedding of Trees
Introduction
Planar Orthogeodesic Pointset Embeddings
Planar $L$ -Shaped Orthogeodesic Pointset Embeddings
Non-Planar $L$ -Shaped Orthogeodesic Point-Set Embeddings
Conclusions
References
On Point-Sets That Support Planar Graphs
Introduction
Preliminaries
Universal Point-Sets for Drawing Planar Graphs with Bends
A Set of $$ (n) Points for Drawing Planar Graphs with Three Bends Per Edge
A Set of $O(nlogn)$ Points for Drawing Planar Graphs with 2 Bends Per Edge
A Set of $O(n2/logn)$ Points for Drawing Planar Graphs with 1 Bend Per Edge
Biconvex Point-Sets and Series-Parallel Graphs
Conclusions and Open Problems
References
Small Point Sets for Simply-Nested Planar Graphs
Introduction
A Universal Point Set for Simply-Nested Planar Graphs with $n_ i$ Vertices on Level $i$
Construction of the Point Set
Embedding a Simply-Nested Planar Graph on Point Set $P$
A Universal Point Set for Simply-Nested Planar Graphs
A Simple Point Set of Size $O(n3/2) $
Further Refinement
Concluding Remarks
References
Graph Visualization
Advances in the Planarization Method: Effective Multiple Edge Insertions
Introduction
Planarization Approach
Engineering
Experiments
References
A Quantitative Comparison of Stress-Minimization Approaches for Offline Dynamic Graph Drawing
Introduction
Offline Dynamic Layout Approaches
Aggregation
Anchoring
Linking
Hypotheses
Experiments
Data
Measurements
Results
Conclusion
References
Accelerated Bend Minimization
Introduction
Bend Minimization and Flow Networks
The Primal Dual Algorithm
A Recursive Approach
References
TGI-EB: A New Framework for Edge Bundling Integrating Topology, Geometry and Importance
Introduction
Related Work
Integrated Framework for Edge Bundling
New Edge Compatibility Measures
The Framework
Centrality Based Edge Bundling (CenEB)
Topology Based Edge Bundling (TopoEB)
Radial Bundling (RadEB)
Orthogonal Edge Bundling (OrthEB)
Time Complexity and Implementation
Experimental Results
Social Networks
Clustered Graphs
Biological Networks
Geographic Networks
Future Work
References
Edge Routing with Ordered Bundles
Introduction
Related Work
Algorithm
Edge Routing
Local Adjustments and Spline Routing
Ordering Paths
Experimental Results
Conclusions and Future Work
References
Right Angle Crossing Graphs and 1-Planarity
Introduction
Red-Blue-Green Coloring of Maximally Dense RAC Graphs
Proof of Theorem 1
Open Problems
References
Pinning Balloons with Perfect Angles and Optimal Area
Introduction
The Greedy Strategy
Splitting the Set of Spokes
The Final Layer
Quality of the Greedy Strategy
Drawing Unordered Trees with Perfect Angles
Concluding Remarks
References
Approximate Proximity Drawings
Introduction and Overview
Problem and Results
Related Work
Approximate Gabriel Drawings
(0,2)-Gabriel Drawings
Approximate -Drawings and Delaunay Drawings
(e1, e2)-ß-Drawings
(e1, e2)- -Drawings
Conclusions and Open Problems
References
Generalizing Geometric Graphs
Introduction
Generalizing the Vertex Set without Vertex-Clutter
Complexity
Approximating the Maximum Size of a Generalization
Minimizing Edge-Clutter
Vertex-Edge-Clutter
Conclusion and Open Problems
References
How to Visualize the K-Root Name Server (Demo)
Introduction
Selecting a Metaphor
The Algorithm
Technical Aspects and User Feedback
State of the Art
Conclusions and Future Work
References
Optimizing a Radial Layout of Bipartite Graphs for a Tool Visualizing Security Alerts
Introduction
Problem Statement
Related Work
Assignment of Concentric Circles to Interior Points
Optimally Connecting an Exterior Point to Interior Ones
Connecting Multiple Exterior Points to Multiple Interior Points
Heuristic I: The Minimum Perfect Matching
Heuristic II: The Anchor Algorithm
Empirical Comparison
Conclusions
References
Visual Community Detection: An Evaluation of 2D, 3D Perspective and 3D Stereoscopic Displays
Introduction
Stereoscopic Perception
Experimental Design
Apparatus
Graph Database
Participants
Experimental Procedure
Results
Quality of Community Detection
Response Time
Participant Perception
Conclusion
References
Evaluating Partially Drawn Links for Directed Graph Edges
Introduction
Related Work
Graph Generation and Layout
Graph Model
Graph Layout
Edge Representation
Link Length
Graph Size
User Experiment
Research Questions
Design
Participants
Study Procedure
Tasks
Results
Conclusion and Future Work
References
Realizing Planar Graphs as Convex Polytopes
Introduction
Inductive Methods
Tutte Embeddings
Stacked Polytopes
Nonlinear Methods
Lower Bounds
References
Overloaded Orthogonal Drawings
Introduction
Overloaded Orthogonal Framework
Compaction
Clarity and Readability of the Model
Directed Acyclic Graphs
Other Graphs
Conclusion and Open Problems
References
Drawing Cubic Graphs with the Four Basic Slopes
Introduction
Proof of Theorem 1
Definitions and Subcubic Theorem
Preliminaries
Proof
Which Four Slopes? and Other Concluding Questions
References
$k$ -Quasi-Planar Graphs
Introduction
Generalized Davenport-Schinzel Sequences
Simple Topological Graphs
$x$ -Monotone
References
Monotone Crossing Number
Introduction
Proof of Theorem 1
Proof of Theorem 2
Concluding Remarks
References
Upper Bound Constructions for Untangling Planar Geometric Graphs
Introduction
Preliminaries
Upper Bound Constructions
($a,b,c$ )-Triangulations
Conclusion
References
Triangulations with Circular Arcs
Introduction
Angle Optimization
Graph-Theoretic Approach
Flipping in Arc Triangles
Special Arc Triangles
Graph Drawing
Open Questions
References
Planar and Poly-arc Lombardi Drawings
Introduction
$k$ -Lombardi Drawings
Non-Lombardi Graphs
Smooth 2-Lombardi Drawings
Planar $k$ -Lombardi Drawings
A Planar 3-Tree with No Planar Lombardi Drawing
Smooth Planar 2-Lombardi Drawings of Planar Max-Degree-3 Graphs
Pointed Planar 2-Lombardi Drawings of Planar Graphs
Smooth Planar 3-Lombardi Drawings of Planar Graphs
Conclusions
References
Force-Directed Lombardi-Style Graph Drawing
Introduction
Related Work
Our Results
A Tangent-Based Lombardi Spring Embedder Formulation
A Tangent-Based Near-Lombardi Spring Embedder
Lombardi Metric
A Dummy-Vertex Approach to Lombardi-Style Drawings
A Comparative Analysis
Conclusion and Future Work
References
Every Graph Admits an Unambiguous Bold Drawing
Introduction
Terminology and Two Preliminary Lemmas
The Main Lemma
The Proof of Theorem 2
References
Adjacent Crossings Do Matter
Introduction
Separating Monotone Crossing Numbers
From Weighted Edges to Unweighted Edges
Adjacent Crossings Are Not Trivial
References
Low Distortion Delaunay Embedding of Trees in Hyperbolic Plane
Introduction
Related Work
Our Contributions
Basics and Notations
Delaunay Embedding of Trees
Delaunay Embedding of Metric Trees
Delaunay Embedding with (1+) Distortion: Hyperbolic Spanner
Conclusion
References
Hardness of Approximate Compaction for Nonplanar Orthogonal Graph Drawings
Introduction
Variations of the Compaction Problem
New Results
Preliminaries
Orthogonal Drawing
Graph Coloring and Inapproximability
Notation
Hardness of Row-by-Row Compaction
Hardness of Vertex-by-Vertex Compaction
Hardness of Vertex-by-Vertex Free Compaction
Hardness of Three-Dimensional Compaction
Approximation Algorithm
Fixed-Parameter Tractability of Vertex-by-Vertex Vertical Compaction
Conclusions
References
Monotone Drawings of Graphs with Fixed Embedding
Introduction
Preliminaries
Monotone Drawings with Bends of Embedded Planar Graphs
Monotone Drawings with Straight-Line Edges
Outerplane Graphs
Biconnected Graphs
Conclusions and Open Problems
References
On the Page Number of Upward Planar Directed Acyclic Graphs
Introduction
Definitions
Page Number and Connectivity
Page Number and Diameter
Page Number and Degree
Conclusions
References
Upward Point Set Embeddability for Convex Point Sets Is in $P$
Introduction
Notation - Preliminaries
Some known Results on UPSE of Rooted Directed Trees
A Restricted UPSE Problem for Rooted Directed Trees
The Testing Algorithm for Directed Trees
Conclusions
References
Classification of Planar Upward Embedding
Introduction
Upward Embeddings with Vector Fields on Surfaces
Classification of Upward Drawings
Complexity
References
Upward Planarity Testing of Embedded Mixed Graphs
Introduction
Definitions and Notation
An ILP Model
Experimental Study
Conclusions and Open Problems
References
Posters
Combining Problems on RAC Drawings and Simultaneous Graph Drawings
Introduction and Problem Definition
Results
References
The Open Graph Archive: A Community-Driven Effort
Introduction
User Needs and Requirements
A Working Prototype: GraphArchive
Outlook
References
Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles
Introduction
Results
References
Viewport for Component Diagrams
Introduction
Viewport for Component Diagrams
Future Work
References
Shortest-Paths Preserving Metro Maps
References
Challenger, a New Way to Visualize Data
Introduction
Implementation
References
Graph Drawing Contest
Graph Drawing Contest Report
Introduction
Angular Resolution
Category A: Straight-Line Planar
Category B: Curved Drawings
Composers Graph
Graph Drawing Challenge
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken