Graph Drawing

The 17th International Symposium on Graph Drawing (GD 2009) was held in Chicago, USA, September 22-25, 2009, and was attended by 91 participants from 19 countries. In response to the call for papers, the Program Committee received 79 s- missions. Each submission was reviewed by at least three Program Committee members. Following substantial discussions, the committee accepted 31 long - pers and 4 short papers. All authors received detailed reviewers' comments. In a separate submission process, 10 posters were accepted. These were described during the conference,and displayedatthe conferencesite. Eachposter was also granted a two-page description in the conference proceedings. Two invited speakers, J anos Pach from EPFL Lausanne and R eny Institute, and Martin Wattenberg from IBM Research, gave absorbing talks during the conference. Prof. Pach looked at the class of string graphs, and tantalized us to consider why their properties are so mathematically beautiful. Dr. Watt- berg showed how sometimes twisting the standard rules of graph drawing can illuminate unexpected information contained in graphs. Keepingwithtradition,the symposiumhostedthe 15thAnnualGraphDr- ingContest,including aGraphDrawingChallengeforconferenceattendees.The contest elicited robust participation from the community with 27 submissions. These proceedings end with a detailed report of the contest. As always, the success of a conference such as this relies on the help of many people. Our thanks to the Program Committee and all of the external referees who worked so hard to sift for the best among the submitted papers. The OrganizingCommittee providedus with admirablefacilities,a ?ne banquet, andtookcareofsomanyotherdetailsthatitwashardtobelievetherewereonly threemembers:Jennifer McClelland,MichaelJ.PelsmajerandMarcusSchaefer.

Inhalt

Invited Talks.- Why Are String Graphs So Beautiful?.- The Art of Cheating When Drawing a Graph.- Papers.- Drawing Hamiltonian Cycles with No Large Angles.- Area, Curve Complexity, and Crossing Resolution of Non-planar Graph Drawings.- On the Perspectives Opened by Right Angle Crossing Drawings.- Drawing 3-Polytopes with Good Vertex Resolution.- Planar Drawings of Higher-Genus Graphs.- Splitting Clusters to Get C-Planarity.- On the Characterization of Level Planar Trees by Minimal Patterns.- Characterization of Unlabeled Radial Level Planar Graphs.- Upward Planarization Layout.- More Flexible Radial Layout.- WiGis: A Framework for Scalable Web-Based Interactive Graph Visualizations.- Port Constraints in Hierarchical Layout of Data Flow Diagrams.- Fast Edge-Routing for Large Graphs.- Leftist Canonical Ordering.- Succinct Greedy Drawings Do Not Always Exist.- Geometric Simultaneous Embeddings of a Graph and a Matching.- Algebraic Methods for Counting Euclidean Embeddings of Rigid Graphs.- Removing Independently Even Crossings.- Manhattan-Geodesic Embedding of Planar Graphs.- Orthogonal Connector Routing.- On Rectilinear Drawing of Graphs.- Semi-bipartite Graph Visualization for Gene Ontology Networks.- On Open Problems in Biological Network Visualization.- A Novel Grid-Based Visualization Approach for Metabolic Networks with Advanced Focus&Context View.- Small Drawings of Series-Parallel Graphs and Other Subclasses of Planar Graphs.- Drawing Trees in a Streaming Model.- The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree.- Drawing Planar 3-Trees with Given Face-Areas.- 3D Visibility Representations by Regular Polygons.- Complexity of Some Geometric and Topological Problems.- On Planar Supports for Hypergraphs.- DAGmaps and ?-Visibility Representations of DAGs.- Drawing Directed Graphs Clockwise.- An Improved Algorithm for the Metro-line Crossing Minimization Problem.- Layout with Circular and Other Non-linear Constraints Using Procrustes Projection.- Posters.- GMap: Drawing Graphs as Maps.- Using High Dimensions to Compare Drawings of Graphs.- On ?-Constrained Upward Topological Book Embeddings.- 4-Labelings and Grid Embeddings of Plane Quadrangulations.- IBM ILOG Graph Layout for Eclipse.- Layout Techniques Coupled with Web2.0-Based Business Process Modeling.- Proving or Disproving Planar Straight-Line Embeddability onto Given Rectangles.- Visualization of Complex BPEL Models.- DAGmaps and Dominance Relationships.- Scaffold Hunter - Interactive Exploration of Chemical Space.- Graph Drawing Contest.- Graph Drawing Contest Report.