Graph Drawing
19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21-23, 2011, Revised Selected Papers
Published on 16. December 2011
XIV, 458 pages
978-3-642-25878-7 (ISBN)
Description
This volume constitutes the refereed proceedings of the 19th International Symposium on Graph Drawing, GD 2010, held in Eindhoven, The Netherlands, during September 2011.
The 34 revised full papers presented together with 3 revised short and 6 poster papers were carefully reviewed and selected from 88 submissions. Furthermore, the proceedings contain the abstracts of two invited talks and to commemorate Kozo Sugiyama and his pioneering research in graph drawing, the proceedings include an obituary. A unique and fun part of the symposium is the Graph Drawing Contest, which is part of the Graph Drawing Challenge. This year was the 18th edition. A report on the contest is included at the end of the proceedings.
The 34 revised full papers presented together with 3 revised short and 6 poster papers were carefully reviewed and selected from 88 submissions. Furthermore, the proceedings contain the abstracts of two invited talks and to commemorate Kozo Sugiyama and his pioneering research in graph drawing, the proceedings include an obituary. A unique and fun part of the symposium is the Graph Drawing Contest, which is part of the Graph Drawing Challenge. This year was the 18th edition. A report on the contest is included at the end of the proceedings.
More details
Other editions
Additional editions
Marc van Kreveld | Bettina Speckmann
Graph Drawing
19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21-23, 2011, Revised Selected Papers
Book
01/2012
Springer
€53.49
Shipment within 7-9 days
Content
- 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
