Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009. Revised Papers

This volume constitutes the refereed proceedings of the 17th International Symposium on Graph Drawing, GD 2009, held in Chicago, USA, during September 2009. The 31 revised full papers and 4 short papers presented were carefully reviewed and selected out of 79 submissions. Furthermore, 10 posters were accepted in a separate submission process. Table of Contents Cover Graph Drawing - 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers ISBN-10 3642118046 ISBN-13 9783642118043 Preface Organization Steering Committee Program Committee Organizing Committee Contest Committee External Referees Sponsoring Institutions Table of Contents Invited Talks Papers Posters Graph Drawing Contest Why Are String Graphs So Beautiful? (Extended Abstract) The Art of Cheating When Drawing a Graph (Extended Abstract) Drawing Hamiltonian Cycles with No Large Angles 1 Introduction 2 Balanced Partitions 3 Making a Tour with Rotation Angles at Most 2p/3 4 CoveringbyTwoAcuteTours 5 Acute Tours for Points in Convex Position 6 Random Point Sets References Area, Curve Complexity, and Crossing Resolution of Non-planar Graph Drawings 1 Introduction 2 Preliminaries 3 Optimal Crossing Resolution: RAC Drawings 4 Nearly Optimal Crossing Resolution: LAC Drawings 5 Open Problems References On the Perspectives Opened by Right Angle Crossing Drawings 1 Introduction 2 Preliminaries 3 Upward RAC Drawings 4 RAC-Drawings of Bounded-Degree Graphs 5 RAC Drawings of Kite-Triangulations 6 Conclusions and Open Problems References Drawing 3-Polytopes with Good Vertex Resolution 1 Introduction 2 Preliminaries: Maxwell and Tutte 3 Extending an Equilibrium Stress to the Boundary 4 Constructing and Controlling an x-Equilibrium Stress 5 The Embedding Algorithm 5.1 The Algorithm Template 5.2 Graphs with Triangular Face 5.3 Graphs with Quadrilateral Face 5.4 The General Case 6 Additional Properties of the Embedding 6.1 Induced Grid Embedding 6.2 Spread of the Embedding References Planar Drawings of Higher-Genus Graphs 1 Introduction 2 Finding Polygonal Schemas 2.1 Trade-O.s for Finding Polygonal Schemas 2.2 Constructing Chord-Free Polygonal Schemas 3 Straight Frame and Polynomial Area 3.1 Grid Embedding of Toroidal Graphs 3.2 The Peel-and-Bend Algorithm 4 Algorithms for Non-toroidal Graphs 5 Conclusion and Future Work References Splitting Clusters to Get C-Planarity 1 Introduction 2 Background 3 General C-Connected Clustered Graphs 4 Series-Parallel C-Connected Clustered Graphs 4.1 Series-Parallel Graphs with Fixed Embedding 4.2 Series-Parallel Graphs with Variable Embedding 5 Non-C-Connected Clustered Graphs 6 Conclusions References On the Characterization of Level Planar Trees by Minimal Patterns 1 Introduction 2 Preliminaries 3 Previous Work 3.1 Characterization of Level Planar Trees by Healy et al. 3.2 Characterization of Level Planar Trees by Fowler and Kobourov 4 New Minimal Level Non-planar Patterns 4.1 Variations of Patterns P3 and P4 4.2 New Pattern P5 5 In nite Minimal Level Non-planar Patterns 6 Conclusions and Future Work References Characterization of Unlabeled Radial Level Planar Graphs (Extended Abstract) 1 Introduction 1.1 Related Previous Work 1.2 Our Contribution 2 Preliminaries 3 Drawing Unlabeled Radial Level Planar Graphs 4 Forbidden Unlabeled Radial Level Planar Graphs 5 Characterizing Unlabeled Radial Level Planar Graphs 5.1 Disconnected Unlabeled Radial Level Planar Graphs 5.2 Connected Unlabeled Radial Level Planar Graphs 6 Conclusion and Future Work References Upward Planarization Layout 1 Introduction 2 Upward Planarization Layout Algorithm 2.1 Layer Assignment and Node Ordering 2.2 Coordinate Assignment 3 Experiments 3.1 Planarization Layouts 3.2 Comparison with Traditional Sugiyama 4 Conclusion References More Flexible Radial Layout 1 Introduction 2 Preliminaries 3 Stress, Weights, and Constraints 3.1 Stress 3.2 Weights for Constraints 3.3 Interpolated Weights 4 RadialLayout 4.1 Target Diagrams 4.2 Centrality Drawings 4.3 Travel Time Maps 5 Conclusion References WiGis: A Framework for Scalable Web-Based Interactive Graph Visualizations 1 Introduction 2 Background 3 Architecture 3.1 Visualization Modes Client-Mode. When a graph in the viewing window (shown in Figure 2) is suf ciently 3.2 System Architecture Layers 3.3 Client/Server Implementations 3.4 Layout 3.5 Interaction 4 Evaluation 4.1 Setup 4.2 Description of Test Data 4.3 Rendering 4.4 Interaction 4.5 Network 4.6 Putting It All Together 4.7 Comparison 5 Discussion and Conclusion Acknowledgements References Port Constraints in Hierarchical Layout of Data Flow Diagrams 1 Introduction 2 Port Constraints and Hyperedges 3 Related Work 4 Extensions of the Hierarchical Layout Approach 4.1 Assignment of Dummy Vertices 4.2 Crossing Minimization 4.3 Orthogonal Edge Routing 4.4 Compound Graphs with External Ports 5 Implementation and Results 6 Conclusion References Fast Edge-Routing for Large Graphs 1 Introduction 2 Related Work 3 A Spatial-Decomposition Routing Scheme 3.1 KD-Tree Partitioning 3.2 Removing Overlaps 3.3 Computing Convex Hulls 3.4 Simplifed Visibility Graphs 3.5 Routing Edges 4 A Sparse Visibility-Graph Spanner 4.1 Balanced Trees of Active Cone Sides and Obstacle Segments 4.2 Algorithm Description 5 Spline Refinemet 6 Experimental Results 7 Conclusion and Further Work References Leftist Canonical Ordering 1 Introduction 2 Preliminaries 2.1 Leftmost Canonical Ordering 2.2 Leftist Canonical Ordering 3 New Algorithm 4 Linear-Time Implementation References Succinct Greedy Drawings Do Not Always Exist 1 Introduction 2 Defnitions and Preliminaries 3 The Lower Bound 3.1 Slopes 3.2 Exponential Decreasing Edge Lengths 4 Drawability of Tn 5 Conclusions References Geometric Simultaneous Embeddings of a Graph and a Matching 1 Introduction 2 Planar Graph and Matching 3 Wheel and Matching 4 Outerzigzag and Matching 5 Outerpath and Matching 6 Tree and Matching 7 Conclusions References Algebraic Methods for Counting Euclidean Embeddings of Rigid Graphs 1 Introduction 2 Planar Embeddings of Laman Graphs 3 An Algebraic Interlude 4 Spatial Embeddings of 1-Skeleta of Simplicial Polyhedra 5 FurtherWork References Removing Independently Even Crossings 1 Crossing Numbers 2 Removing Even More Crossings References Manhattan-Geodesic Embedding of Planar Graphs 1 Introduction 2 Geodesic Embeddability 3 Geodesic Point-Set Embeddability 4 Labeled Geodesic Point-Set Embeddability References Orthogonal Connector Routing 1 Introduction 2 Problem Statement 3 Orthogonal Visibility Graph 4 Routing the Connector 5 Computing the Visual Representation 5.1 Ordering Shared Edges 5.2 Final Placement 6 Evaluation 7 Related Work 8 Conclusion References On Rectilinear Drawing of Graphs 1 Introduction 2 Some Basic Properties 2.1 Four-Cycle Covers and Blocks 2.2 Density 2.3 Area 3 Graphs with a Connected-4-Cycle Cover 4 Hardness Results 4.1 Graphs of 4-Cycle Blocks Connected by Edges 4.2 Graphs with Degree-2 and Degree-4 Vertices 5 Fixed-Parameter Algorithm 6 Conclusion References Semi-bipartite Graph Visualization for Gene Ontology Networks 1 Introduction 2 Related Work 2.1 Gene Ontology Visualization 2.2 Layered Drawings and Sugiyama Method 3 Semi-bipartite Graph and Gene-Term Network 4 Layout Algorithms for Semi-bipartite Graphs 4.1 Extended Bipartite Algorithms 4.2 Sub-hierarchy Barycenter Algorithm 4.3 Partition Merge Algorithm 5 Term Reduction 6 Evaluation 6.1 Dataset 6.2 Implementation 6.3 Layout Quality 6.4 Term Reduction 6.5 Running Time 6.6 User Feedback 7 Conclusions References On Open Problems in Biological Network Visualization 1 Introduction 2 The Nature of Biological Network Data 2.1 Types of Biological Networks 2.2 The Attributes of Network Elements 3 Use Cases and Related Visualization Problems 3.1 Visual Analysis of Data Correlation 3.2 Visual Comparison of Similar Biological Networks 3.3 Integrated Representation of Multiple Overlapping Networks 3.4 Visualization of Sub-cellular Localization 3.5 Visualization of Multiple Attributes 3.6 Visualization of Flows and Paths in Networks 3.7 Exploration of Hierarchical Networks 4 Conclusions Acknowledgements References A Novel Grid-Based Visualization Approach for Metabolic Networks with Advanced Focus&Context View 1 Introduction 2 Related Work 3 Network Data Source 4 Hierarchical Orthogonal Grid Layout 5 Graph Interaction 5.1 Exploration Techniques 5.2 Design of the Graphical User Interface 6 PerformanceResults 7 Conclusion References Small Drawings of Series-Parallel Graphs and Other Subclasses of Planar Graphs 1 Introduction 2 Background 3 Visibility Representations of Series-Parallel Graphs 4 Lower Bounds References Drawing Trees in a Streaming Model 1 Introduction 2 Framework 3 Finite Persistence Drawings of Trees 4 Infinte Persistence Drawings of Trees 4.1 Arbitrary Order Scenario 4.2 BFS and DFS Order Scenarios 4.3 Layer Order 5 Open Problems Acknowledgments References The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree 1 Introduction 2 Series-Parallel Graphs 3 Planar 3-Trees 4 Conclusion and Open Problems References Drawing Planar 3-Trees with Given Face-Areas 1 Introduction 2 Background 3 Drawing Planar Partial 3-Trees 4 Negative Results References 3 D Visibility Representations by Regular Polygons 1 Introduction 2 Preliminaries 3 Regular2k-gons 4 Regular(2k + 1)-gons 5 Conclusion References Complexity of Some Geometric and Topological Problems 1 Introduction 2 Background 3 Rectilinear Crossing Number 4 Intersection Graphs of Segments 5 Intersection Graphs of Convex Sets 6 Topological Inference References On Planar Supports for Hypergraphs 1 Introduction 2 Path, Cycle, and Tree Supports 3 Bounded-Degree Tree Supports 4 Hardness for 3-Outerplanar Graphs References DAGmaps and e-Visibility Representations of DAGs 1 Introduction 2 Preliminaries 3 One-Dimensional DAGmaps and Directed e-Visibility Representations 4 Characterization of Directed e-Visibility Representations 5 Characterization of One-Dimensional DAGmaps 6 DAGmaps and Three Dimensional e-Visibility Representations 7 Discussion References Drawing Directed Graphs Clockwise 1 Introduction 2 Preliminaries 3 Skew-Symmetry 4 Clockwise Drawings 5 Implementation 6 An Application 7 Conclusion References An Improved Algorithm for the Metro-line Crossing Minimization Problem 1 Introduction 2 Model 3 MLCM Variants and Previous Work 4 An Improved Algorithm for MLCM-PA 5 Conclusions References Layout with Circular and Other Non-linear Constraints Using Procrustes Projection 1 Introduction 2 Related Work 3 Constraint Projection 3.1 Separation Constraint Projection 3.2 Euclidean Distance Projection 4 Procrustes Projection 4.1 Choosing the Target Configuraton 5 Combining Constraints in an Incremental Layout Step 5.1 Gauss-Seidel Gradient Projection 5.2 Separation Constraint Projection 6 Discussion, Conclusion, Further Work References GMap: Drawing Graphs as Maps 1 Introduction 2 The Mapping and Coloring Algorithm 3 GMapExample References Using High Dimensions to Compare Drawings of Graphs 1 Introduction 2 Algorithm 3 Applications References On rho-Constrained Upward Topological Book Embeddings 1 Introduction 2 Results References 4-Labelings and Grid Embeddings of Plane Quadrangulations References IBM ILOG Graph Layout for Eclipse 1 Introduction 2 Highlights Layout Techniques Coupled with Web2.0-Based Business Process Modeling 1 Introduction 2 Oryx - A Web2.0-Based Collaborative Graphical Editor 3 The Automatic Layout Algorithm and Integration into Oryx References Proving or Disproving Planar Straight-Line Embeddability onto Given Rectangles Encoding as SAT Problem Experimental Results and Conclusion References Visualization of Complex BPEL Models 1 Introduction 2 Collaborative Workflo Development with HOBBES 3 Realizing Layout Capabilities in Hobbes References DAGmaps and Dominance Relationships 1 Introduction 2 Transforming a DAG So That It Admits a DAGmap References Scaffold Hunter - Interactive Exploration of Chemical Space References Graph Drawing Contest Report 1 Introduction 2 SimpleTree 3 Organization Chart 4 FlowChart 5 MysteryGraph 6 Graph Drawing Challenge References Author Index