Graph Drawing

1. Front Matter

   Pages I-XIV

   PDF

2. Invited Talks

   1. Networks in Biology – From Identification, Analysis to Interpretation

      • Jesper Tegnér

      Pages 1-1

   2. Graph Drawing for Security Visualization

      • Roberto Tamassia, Bernardo Palazzi, Charalampos Papamanthou

      Pages 2-13

3. Papers

   1. Succinct Greedy Graph Drawing in the Hyperbolic Plane

      • David Eppstein, Michael T. Goodrich

      Pages 14-25

   2. An Algorithm to Construct Greedy Drawings of Triangulations

      • Patrizio Angelini, Fabrizio Frati, Luca Grilli

      Pages 26-37

   3. Crossing and Weighted Crossing Number of Near-Planar Graphs

      • Sergio Cabello, Bojan Mohar

      Pages 38-49

   4. Cubic Graphs Have Bounded Slope Parameter

      • Balázs Keszegh, János Pach, Dömötör Pálvölgyi, Géza Tóth

      Pages 50-60

   5. Unimaximal Sequences of Pairs in Rectangle Visibility Drawing

      • Jan Štola

      Pages 61-66

   6. Visibility Representations of Four-Connected Plane Graphs with Near Optimal Heights

      • Chieh-Yu Chen, Ya-Fei Hung, Hsueh-I Lu

      Pages 67-77

   7. The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing

      • David Eppstein

      Pages 78-89

   8. Rapid Multipole Graph Drawing on the GPU

      • Apeksha Godiyal, Jared Hoberock, Michael Garland, John C. Hart

      Pages 90-101

   9. Clustered Planarity: Clusters with Few Outgoing Edges

      • Vít Jelínek, Ondřej Suchý, Marek Tesař, Tomáš Vyskočil

      Pages 102-113

   10. Computing Maximum C-Planar Subgraphs

       • Markus Chimani, Carsten Gutwenger, Mathias Jansen, Karsten Klein, Petra Mutzel

       Pages 114-120

   11. Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters

       • Vít Jelínek, Eva Jelínková, Jan Kratochvíl, Bernard Lidický

       Pages 121-132

   12. Visual Analysis of One-to-Many Matched Graphs

       • Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Pietro Palladino

       Pages 133-144

   13. Topological Morphing of Planar Graphs

       • Patrizio Angelini, Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani

       Pages 145-156

   14. An SPQR-Tree Approach to Decide Special Cases of Simultaneous Embedding with Fixed Edges

       • J. Joseph Fowler, Carsten Gutwenger, Michael Jünger, Petra Mutzel, Michael Schulz

       Pages 157-168

   15. Graph Simultaneous Embedding Tool, GraphSET

       • Alejandro Estrella-Balderrama, J. Joseph Fowler, Stephen G. Kobourov

       Pages 169-180

   16. Hamiltonian Alternating Paths on Bicolored Double-Chains

       • Josef Cibulka, Jan Kynčl, Viola Mészáros, Rudolf Stolař, Pavel Valtr

       Pages 181-192

   17. The Binary Stress Model for Graph Drawing

       • Yehuda Koren, Ali Çivril

       Pages 193-205

The 16th International Symposium on Graph Drawing (GD 2008) was held in Hersonissos, near Heraklion, Crete, Greece, September 21-24, 2008, and was attended by 91 participants from 19 countries. In response to the call for papers the Program Committee received 83 s- missions,eachdescribing originalresearchand/or a systemdemonstration.Each submissionwasreviewedbyatleastthreeProgramCommitteemembersandthe reviewer’s comments were returned to the authors. Following extensive disc- sions, the committee accepted 31 long papers and 8 short papers. In addition, 10 posters were accepted and displayed at the conference site. Each poster was granted a two-page description in the conference proceedings. Two invited speakers, Jesper Tegn´ er from Karolinska Institute (Monday) and Roberto Tamassia from Brown University (Tuesday), gave fascinating talks during the conference. Professor Tegn´ er focused on the challenges and oppor- nities posed by the discovery, analysis, and interpretation of biological networks to information visualization, while Prof. Tamassia showed how graph drawing techniques can be used as an e?ective tool in computer security and pointed to future research directions in this area. Following what is now a tradition, the 15th Annual Graph Drawing Contest was held during the conference, also including a Graph Drawing Challenge to the conference attendees. A report is included in the conference proceedings.

• GPU
• Layout
• Triangulation
• algorithmic graph theory
• algorithms
• alternating path
• calculus
• clusters
• computational graph theory
• constrained optimization
• directed graphs
• graph coloring
• graph comput
• topology
• visualization
• algorithm analysis and problem complexity
• data structures

• University of Crete, Department of Computer Science, 71409 Heraklion, Crete, Greece, and, Institute of Computer Science, Foundation for research and Technology-Hellas (FORTH), Science and Technology Park of Crete, 71110 Heraklion, Crete,, Greece

  Ioannis G. Tollis

• Dip. Informatica e Automazione, Università Roma Tre, Rome, Italy

  Maurizio Patrignani

Policies and ethics