Graph Drawing: 15th International Symposium, GD 2007, Sydney, Australia, September 24-26, 2007. Revised Papers

Brendan D. McKay (auth.), Seok-Hee Hong, Takao Nishizeki, Wu Quan (eds.)9783540775362, 3540775366

This book constitutes the thoroughly refereed post-conference proceedings of the 15th International Symposium on Graph Drawing, GD 2007, held in Sydney, Australia, September 24-26, 2007.

The 27 full papers and 9 short papers presented together with 2 invited talks, and a report on the graph drawing contest were carefully selected from 74 initial submissions. All current aspects in graph drawing are addressed ranging from foundational and methodological issues to applications for various classes of graphs in a variety of fields.

---

Table of contents :
Front Matter….Pages –
Computing Symmetries of Combinatorial Objects….Pages 1-1
Large-Scale Graphics: Digital Nature and Laser Projection….Pages 2-2
Crossing Number of Graphs with Rotation Systems….Pages 3-12
A Bipartite Strengthening of the Crossing Lemma….Pages 13-24
Improvement on the Decay of Crossing Numbers….Pages 25-30
Crossing Numbers and Parameterized Complexity….Pages 31-36
Characterization of Unlabeled Level Planar Graphs….Pages 37-49
Cyclic Level Planarity Testing and Embedding….Pages 50-61
Practical Level Planarity Testing and Layout with Embedding Constraints….Pages 62-68
Minimum Level Nonplanar Patterns for Trees….Pages 69-75
Straight-Line Orthogonal Drawings of Binary and Ternary Trees….Pages 76-87
Polynomial Area Bounds for MST Embeddings of Trees….Pages 88-100
Moving Vertices to Make Drawings Plane….Pages 101-112
Point-Set Embedding of Trees with Edge Constraints….Pages 113-124
Representation of Planar Hypergraphs by Contacts of Triangles….Pages 125-136
The Complexity of Several Realizability Problems for Abstract Topological Graphs….Pages 137-158
Efficient Extraction of Multiple Kuratowski Subdivisions….Pages 159-170
Cover Contact Graphs….Pages 171-182
Matched Drawings of Planar Graphs….Pages 183-194
Maximum Upward Planar Subgraphs of Embedded Planar Digraphs….Pages 195-206
Minimizing the Area for Planar Straight-Line Grid Drawings….Pages 207-212
On Planar Polyline Drawings….Pages 213-218
Constrained Stress Majorization Using Diagonally Scaled Gradient Projection….Pages 219-230
Line Crossing Minimization on Metro Maps….Pages 231-242
Algorithms for Multi-criteria One-Sided Boundary Labeling….Pages 243-254
Multi-circular Layout of Micro/Macro Graphs….Pages 255-267
Constrained Simultaneous and Near-Simultaneous Embeddings….Pages 268-279
Simultaneous Geometric Graph Embeddings….Pages 280-290
Efficient C-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces….Pages 291-302
Clustered Planarity: Small Clusters in Eulerian Graphs….Pages 303-314
Drawing Colored Graphs with Constrained Vertex Positions and Few Bends per Edge….Pages 315-326
Colorability in Orthogonal Graph Drawing….Pages 327-338
A Note on Minimum-Area Straight-Line Drawings of Planar Graphs….Pages 339-344
Universal Sets of n Points for 1-Bend Drawings of Planar Graphs with n Vertices….Pages 345-351
LunarVis – Analytic Visualizations of Large Graphs….Pages 352-364
Visualizing Internet Evolution on the Autonomous Systems Level….Pages 365-376
Treemaps for Directed Acyclic Graphs….Pages 377-388
Drawing Graphs with GLEE….Pages 389-394
Graph Drawing Contest Report….Pages 395-400
Back Matter….Pages –