Graph Drawing
18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010. Revised Selected Papers
Published on 10. February 2011
XIV, 414 pages
978-3-642-18469-7 (ISBN)
Description
This volume constitutes the refereed proceedings of the 18th
International Symposium on Graph Drawing, GD 2010, held in Konstanz,
Germany, during September 2010.
The 30 revised full papers presented together with 5 revised short and 8
poster papers were carefully reviewed and selected from 77 submissions.
The volume also contains a detailed report about the 17th Annual Graph
Drawing Contest, held as a satellite event of GD 2010. Devoted both to
theoretical advances as well as to implemented solutions, the papers are
concerned with the geometric representation of graphs and networks and
are motivated by those applications where it is crucial to visualize
structural information as graphs.
More details
Other editions
Additional editions
Ulrik Brandes | Sabine Cornelsen
Graph Drawing
18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010. Revised Selected Papers
Book
01/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- 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
