Lecture Notes in Computer Science 1547 Editedby G.Goos,J. Hartmanisand J.van Leeuwen 3 Berlin Heidelberg NewYork Barcelona HongKong London Milan Paris Singapore Tokyo Sue H. Whitesides (Ed.) Graph Drawing 6th International Symposium, GD ’98 Montre´al, Canada, August 13-15, 1998 Proceedings 1 3 SeriesEditors GerhardGoos,KarlsruheUniversity,Germany JurisHartmanis,CornellUniversity,NY,USA JanvanLeeuwen,UtrechtUniversity,TheNetherlands VolumeEditor SueH.Whitesides SchoolofComputerScience,McGillUniversity 3480UniversitySt.#318,Montre´al,Que´becH3A2A7,Canada E-mail:[email protected] Cataloging-in-Publicationdataappliedfor DieDeutscheBibliothek-CIP-Einheitsaufnahme Graphdrawing:6thinternationalsymposium;proceedings/GD’98,Montre´al, Canada,August13-15,1998.SueH.Whitesides(ed.).-Berlin;Heidelberg; NewYork;Barcelona;HongKong;London;Milan;Paris;Singapore;Tokyo: Springer,1999 (Lecturenotesincomputerscience;Vol.1547) ISBN3-540-65473-9 CRSubjectClassification(1998):I.4,I.2.9-10,I.3.1,C.3 ISSN0302-9743 ISBN3-540-65473-9Springer-VerlagBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer-Verlag.Violationsare liableforprosecutionundertheGermanCopyrightLaw. (cid:1)c Springer-VerlagBerlinHeidelberg1999 PrintedinGermany Typesetting:Camera-readybyauthor SPIN10693106 06/3142–543210 Printedonacid-freepaper Preface Graphdrawingaddressestheproblemofconstructingrepresentationsofabstract graphs, networks, and hypergraphs. The 6th Symposium on Graph Drawing (GD ’98) was held August 13{15, 1998,atMcGillUniversity,Montr(cid:19)eal,Canada.ItimmediatelyfollowedtheTenth Canadian Conference on Computational Geometry (CCCG ’98), held August 10{12 at McGill. The GD ’98 conference attracted 100 paid registrants from academicandindustrialinstitutions in thirteencountries.Roughlyhalf the par- ticipantsalsoattendedCCCG’98.Asinthepast,interactionamongresearchers, practitioners,andstudentsfromtheoreticalcomputerscience,mathematics,and the application areas of graph drawing continued to be an important aspect of the graph drawing symposium. In response to the call for papers and system demonstrations, the program committee received 57 submissions, of which 10 were demos. Each submission was reviewed by at least 4 members of the program committee, and comments werereturnedtotheauthors.Followingextensiveemaildiscussionsandmultiple rounds of voting, the program committee accepted 23 papers and 9 demos. GD ’98 also held an unrefereed poster gallery. The poster gallery contained 16 posters,14 of which have abstracts in this volume. The poster gallery served toencourageparticipationfromresearchersinrelatedareasandprovidedastim- ulating environment for the breaks between the technical sessions. Inkeeping with the traditionofprevious graphdrawingconferences,GD ’98 held a graph drawing contest. This contest, which is traditionally a conference highlight,servestomonitorandtochallengethestateoftheartingraphdrawing. A report on the 1998 contest appears in this volume. Many people in the graph drawing community contributed to the success of GD ’98. In particular, the authors of submitted papers, demos, and posters are due special thanks, as are the members of the program committee and the referees it consulted. Much thought and care went into the selection of a high quality technical program. VeryspecialthanksareduetoSteveRobbins,whohandledtheWebsite,the electronicsubmissionprocess,andthe equipmentfor the demos,andto Therese Biedl, whose hard work and e(cid:14)ciency were indispensible to the success of the conference. She also organized the poster gallery and designed the logos. Thanks are also due many people in the McGill community for their contri- butions. It was a pleasure to work with volunteers from the newly formed ACM student chapter at McGill. These volunteers ran errands and provided sta(cid:14)ng throughout the conference. Special thanks are due to Albert Mah, who coordi- nated the volunteers and contributed many useful suggestions. Fran(cid:24)cois Labelle arranged publicity announcements. Michael Soss of the CCCG ’98 organizing committee provided coordination with that conference. VI Preface Judy Kenigsberg and Lucy St. James of the McGill University School of Computer Science sta(cid:11) provided administrative support. Lucy St. James han- dled preconference registration. Judy Kenisberg, who sta(cid:11)ed the registration andinformationbooth, contributedheartand soulto the conference,pulled the team together,befriended the participants,and providedexcellentsta(cid:11) support throughout. Thanks are due to the sta(cid:11) of the Redpath Museum, where the conference washeld,andtothesta(cid:11)ofThomsonHouse,wheretheluncheswereheld.Dean of Science Alan Shaver, who gave the opening remarks, also provided (cid:12)nancial backing and suggested the Redpath Museum as a conference venue. Iwishto thank these people andallthe many otherswho contributedto the success of the conference. GD ’99 is to be held in the Czech Republic, September 15{19, 1999, under the sponsorship of DIMATIA and Charles University, with Jan Kratochv(cid:19)(cid:16)l as conference chair. Montr(cid:19)eal,October 1998 Sue Whitesides ProgramCommittee Chair Organizing Committee Chair GD ’98 Program Committee Franz Brandenburg (Univerity of Passau,Germany) Peter Eades (University of Newcastle, Australia) Emden Gansner (AT&T, USA) Michael Kaufmann (University of Tu¨bingen, Germany) Giuseppe Liotta (University of Rome \La Sapienza", Italy) Anna Lubiw (University of Waterloo, Canada) Brendan Madden (Tom Sawyer Software, USA) Joe Marks (Mitsubishi Electric, USA) Shin-ichi Nakano (Tohoku University, Japan) Ja(cid:19)nos Pach (NYU, USA) Roberto Tamassia (Brown University, USA) Ioannis G. Tollis (The University of Texas at Dallas, USA) Dorothea Wagner (University of Constance, Germany) Sue Whitesides, chair (McGill University, Canada) Organizing Committee Therese Biedl (McGill University, Canada) Prosenjit Bose (Carleton University, Canada ) Franc(cid:24)ois Labelle (McGill University, Canada ) Sylvain Lazard (McGill University, Canada) Giuseppe Liotta (University of Rome \La Sapienza", Italy) Steve Robbins (McGill University, Canada) Sue Whitesides (McGill University, Canada) Graph Drawing Contest Organizers Peter Eades (University of Newcastle, Australia) Joe Marks (Mitsubishi Electric, USA) Petra Mutzel (Max Planck Institute for Computer Science, Germany) Stephen North (AT&T, USA) Poster Gallery Organizer Therese Biedl (McGill University, Canada) Steering Committee Franz J. Brandenburg (University of Passau,Germany) Giuseppe Di Battista (University of Rome Tre, Italy) Peter Eades (University of Newcastle, Australia) Jan Kratochv(cid:19)(cid:16)l(Charles University, Czech Republic) Joe Marks (Mitsubishi Electric, USA) Roberto Tamassia (Brown University, USA) Ioannis Tollis (The University of Texas at Dallas, USA) Sue Whitesides (McGill University, Canada) Arrangements and Registration Judy Kenigsberg (McGill University, Canada) Lucy St. James (McGill University, Canada) Volunteers Ehab Abdul-Baki Julianna Lin Gilles Pesant Kathleen Botter Albert Mah Uri Pizarro Frank Eory Minou Mansouri Michael Soss Abeer Ghuneim Anouk Mercier Monica Giannikakis C(cid:19)ecile Morin VIII Preface Sponsor McGill University, Faculty of Science Additional Referees W. Bachl C. Iturriaga G. Toth T. Biedl K. Kakoulis L. Vismara U. Brandes H. Lauer K. Weihe E. Demaine A. Liebers R. Wiese E. Dengler P. Mutzel S. Wetzel W. Didimo M. Patrignani T. Willhalm D. Handke R. Pollack T. Wurst M. Himsolt A. Quigley A. Zell S. Hong B. Regan M. Houle F. Schreiber M. L. Huang J. Six Contents Papers Drawing of Two-Dimensional Irregular Meshes ............................. 1 Alok Aggarwal, S. Rao Kosaraju, and Mihai Pop Quasi-UpwardPlanarity .................................................. 15 Paola Bertolazzi, Giuseppe Di Battista, and Walter Didimo Three Approaches to 3D-OrthogonalBox-Drawings ....................... 30 Therese C. Biedl Using Graph Layout to Visualize Train Interconnection Data .............. 44 Ulrik Brandes and Dorothea Wagner Difference Metrics for Interactive Orthogonal Graph Drawing Algorithms ...................................................... 57 Stina Bridgeman and Roberto Tamassia Upward Planarity Checking: “Faces Are More than Polygons” ............. 72 Giuseppe Di Battista and Giuseppe Liotta A Split&Push Approach to 3D OrthogonalDrawing ....................... 87 Giuseppe Di Battista, Maurizio Patrignani, and Francesco Vargiu Geometric Thickness of Complete Graphs ................................ 102 Michael B. Dillencourt, David Eppstein, and Daniel S. Hirschberg Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs ............................................. 111 Christian A. Duncan, Michael T. Goodrich, and Stephen G. Kobourov On Improving OrthogonalDrawings: The 4M-Algorithm ................. 125 Ulrich Fo¨ßmeier, Carsten Heß, and Michael Kaufmann Algorithmic Patterns for Graph Drawing ................................. 138 Natasha Gelfand and Roberto Tamassia A Framework for Drawing Planar Graphs with Curves and Polylines ..... 153 Michael T. Goodrich and Christopher G. Wagner Planar Polyline Drawings with Good Angular Resolution ................. 167 Carsten Gutwenger and Petra Mutzel A Layout Adjustment Problem for Disjoint Rectangles Preserving Orthogonal Order ............................................ 183 Kunihiko Hayashi, Michiko Inoue, Toshimitsu Masuzawa, and Hideo Fujiwara X Contents Drawing Algorithms for Series-ParallelDigraphs in Two and Three Dimensions ........................................... 198 Seok-Hee Hong, Peter Eades, Aaron Quigley, and Sang-Ho Lee Approximation Algorithms for Finding Best Viewpoints .................. 210 Michael E. Houle and Richard Webber Level Planarity Testing in Linear Time ................................... 224 Michael Ju¨nger, Sebastian Leipert, and Petra Mutzel Crossing Number of Abstract TopologicalGraphs ........................ 238 Jan Kratochv´ıl Self-Organizing Graphs – A Neural Network Perspective of Graph Layout ......................................................... 246 Bernd Meyer Embedding Planar Graphs at Fixed Vertex Locations .................... 263 Janos P´ach and Rephael Wenger Proximity Drawings: Three Dimensions Are Better than Two ............ 275 Paolo Penna and Paola Vocca NP-Completeness of Some Tree-Clustering Problems ..................... 288 F. Schreiber and K. Skodinis Refinement of OrthogonalGraph Drawings ............................... 302 Janet M. Six, Konstantinos G. Kakoulis, and Ioannis G. Tollis A Combinatorial Framework for Map Labeling ........................... 316 Frank Wagner and Alexander Wolff An Algorithm for Three-Dimensional OrthogonalGraph Drawing ........ 332 David R. Wood System Demonstrations Graph Multidrawing: Finding Nice Drawings without Defining Nice ...... 347 Therese Biedl, Joe Marks, Kathy Ryall, and Sue Whitesides Edge Labeling in the Graph Layout Toolkit .............................. 356 U˘gur Do˘gruso¨z, Konstantinos G. Kakoulis, Brendan Madden, and Ioannis G. Tollis Improved Force-Directed Layouts ........................................ 364 Emden R. Gansner and Stephen C. North A Fully Animated Interactive System for Clustering and Navigating Huge Graphs ............................................ 374 Mao Lin Huang and Peter Eades Drawing Large Graphs with H3Viewer and Site Manager ................. 384 Tamara Munzner