Therese Biedl Andreas Kerren (Eds.) 2 8 2 1 Graph Drawing 1 S C and Network Visualization N L 26th International Symposium, GD 2018 Barcelona, Spain, September 26–28, 2018 Proceedings 123 Lecture Notes in Computer Science 11282 Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen Editorial Board David Hutchison Lancaster University, Lancaster, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Friedemann Mattern ETH Zurich, Zurich, Switzerland John C. Mitchell Stanford University, Stanford, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel C. Pandu Rangan Indian Institute of Technology Madras, Chennai, India Bernhard Steffen TU Dortmund University, Dortmund, Germany Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Gerhard Weikum Max Planck Institute for Informatics, Saarbrücken, Germany More information about this series at http://www.springer.com/series/7407 Therese Biedl Andreas Kerren (Eds.) (cid:129) Graph Drawing and Network Visualization 26th International Symposium, GD 2018 – Barcelona, Spain, September 26 28, 2018 Proceedings 123 Editors Therese Biedl Andreas Kerren University of Waterloo Linnaeus University Waterloo, ON,Canada Växjö,Sweden ISSN 0302-9743 ISSN 1611-3349 (electronic) Lecture Notesin Computer Science ISBN 978-3-030-04413-8 ISBN978-3-030-04414-5 (eBook) https://doi.org/10.1007/978-3-030-04414-5 LibraryofCongressControlNumber:2018961593 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ©SpringerNatureSwitzerlandAG2018 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartofthe material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodologynow knownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthors,andtheeditorsaresafetoassumethattheadviceandinformationinthisbookare believedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsortheeditors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissionsthatmayhavebeenmade.Thepublisherremainsneutralwithregardtojurisdictionalclaimsin publishedmapsandinstitutionalaffiliations. ThisSpringerimprintispublishedbytheregisteredcompanySpringerNatureSwitzerlandAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Preface ThisvolumecontainsthepaperspresentedatGD2018:26thInternationalSymposium onGraphDrawing andNetworkVisualizationheld duringSeptember26–28,2018,in Barcelona. Graph drawing is concerned with the geometric representation of graphs and constitutes the algorithmic core of network visualization. Graph drawing and network visualization are motivated by applications where it is crucial to visually analyze and interact with relational datasets. Information about the conference series and past symposia is maintained at http://www.graphdrawing.org. The 2018 edition of the conference was hosted by Universitat Politècnica de Catalunya, with Vera SacristánandRodrigoSilveiraasco-chairsoftheOrganizingCommittee.Atotalof99 participants attended the conference. Regularpaperscouldbesubmitted tooneoftwodistinct tracks:Track1forpapers on combinatorial and algorithmic aspects of graph drawing and Track 2 for papers on experimental, applied, and network visualization aspects. Short papers were given a separate category, which welcomed both theoretical and applied contributions. An additional track was devoted to poster submissions. All the tracks were handled by a single ProgramCommittee. Inresponsetothecall forpapers,theProgram Committee receivedatotalof102submissions,consistingof85papers(45inTrack1,23inTrack 2, and 17 in the short paper category; two papers that were withdrawn by the authors are not included in these statistics) and 17 posters. More than 330 expert single-blind reviews were provided, roughly a third of which were contributed by external sub-reviewers. After extensive electronic discussions via EasyChair, the Program Committeeselected41papersand14postersforinclusioninthescientificprogramof GD 2018. This resulted in an overall paper acceptance rate of 48% (58% in Track 1, 43%inTrack2,and29%intheshortpapercategory).Authorspublishedanelectronic version of their accepted papers on an arXiv repository; a conference index with links to these contributions was made available before the conference. There were two keynote talks at GD 2018. Alexandru Telea, from University of Groningen, The Netherlands, talked about methods for “Image-Based Graph Visual- ization: Advances and Challenge.” Bojan Mohar, from Simon Fraser University, Canada,spokeaboutthe“BeautyandChallengesofCrossingNumbers.”Theabstracts of both talks are included in the proceedings. The conference gave out best paper awards in Track 1 and Track 2, plus a best presentation award and a best poster award. As decided by a subcommittee of the Program Committee, the award for the best paper in Track 1 was assigned to “Pole Dancing: 3D Morphs for Tree Drawings” by Elena Arseneva, Prosenjit Bose, Pilar Cano, Anthony D’Angelo, Vida Dujmović, Fabrizio Frati, Stefan Langerman, and Alessandra Tappini, and the award for the best paper in Track 2 was assigned to “Aesthetic Discrimination of Graph Layouts” by Moritz Klammler, Tamara Mche- dlidze, and Alexey Pak. The participants of the conference voted to determine as the bestpresentationtheonegivenjointlybyElenaArsenevaandPilarCanoforthepaper VI Preface “Pole Dancing: 3D Morphs for Tree Drawings” and as the best poster the one by Charles Camacho, Silvia Fernández-Merchant, Marija Jelic, Rachel Kirsch, Linda Kleist, Elizabeth Bailey Matson, and Jennifer White entitled “Bounding the Tripartite-Circle CrossingNumberofComplete Tripartite Graphs.” Congratulations to alltheawardwinnersfortheirexcellentcontributions,andmanythankstoSpringerand MDPI whose sponsorship funded the prize money for these awards. Following the tradition, the 25th Annual Graph Drawing Contest was held during the conference. The contest was divided into two parts, creative topics and the live challenge. The creative topics featured two graphs, one about Games of Thrones and oneabouttheMathematicsGenealogyProject.Thelivechallengefocusedondrawings that maximize the crossing-angles, and had two categories: manual and automatic. Awards were given in each of the four categories. We thank the Contest Committee, chairedbyMaartenLöffler,forpreparinginterestingandchallengingcontestproblems. A report about the contest is included in these proceedings. Many people and organizations contributed to the success of GD 2018. We would liketothanktheProgramCommitteemembersandtheexternalreviewersforcarefully reviewinganddiscussingthesubmittedpapersandposters;thiswascrucialforputting together a strong and interesting program. Thanks to all the authors who chose GD 2018asthepublicationvenuefortheirresearch.Weareindebtedtothegoldsponsors Tom Sawyer Software and yWorks, the silver sponsor Microsoft, and the bronze sponsorSpringer.Theirgeneroussupporthelpstoensurethecontinuedsuccessofthis conference. Last but not least, the organizing co-chairs, Vera Sacristán and Rodrigo Silveira,didaterrificjob;theyinturnwouldliketoexpresstheirthankstootherlocal organizers and volunteers, including Therese Biedl, Pilar Cano, Karla García, Carmen Hernando, Clemens Huemer, Maarten Löffler, Mercè Mora, Carlos Seara, and Roger Solí. The 27th International Symposium on Graph Drawing and Network Visualization (GD 2019) will take place September 17–20, 2019 in Průhonice (near Prague), Czech Republic. Daniel Archambault and Csaba Tóth will co-chair the Program Committee. Jiří Fiala and Pavel Valtr will co-chair the Organizing Committee. October 2018 Therese Biedl Andreas Kerren Organization Steering Committee Daniel Archambault Swansea University, UK Therese Biedl University of Waterloo, Canada Giuseppe Di Battista Università Roma Tre, Italy Fabrizio Frati Università Roma Tre, Italy Andreas Kerren Linnaeus University, Sweden Stephen G. Kobourov University of Arizona, USA (Incoming Chair) Giuseppe Liotta (Outgoing Università di Perugia, Italy Chair) Kwan-Liu Ma University of California at Davis, USA Martin Nöllenburg Technische Universität Wien, Austria Roberto Tamassia Brown University, USA Ioannis G. Tollis UniversityofCrete,GreeceandTomSawyerSoftware, USA Csaba D. Tóth California State University Northridge, USA Program Committee Patrizio Angelini Tübingen University, Germany Daniel Archambault Swansea University, UK David Auber LaBRI, Université Bordeaux, France Therese Biedl (Co-chair) University of Waterloo, Canada Carla Binucci University of Perugia, Italy Erin Chambers Saint Louis University, USA Steven Chaplick Universität Würzburg, Germany Giuseppe Di Battista Università Roma Tre, Italy Tim Dwyer Monash University, Australia Radoslav Fulek IST Austria, Austria Christophe Hurter ENAC – École Nationale de l’Aviation Civile, France Andreas Kerren (Co-chair) Linnaeus University, Sweden Karsten Klein University of Konstanz, Germany Debajyoti Mondal University of Saskatchewan, Canada Petra Mutzel TU Dortmund University, Germany Yoshio Okamoto The University of Electro-Communications and RIKEN Center for Advanced Intelligence Project (AIP), Japan Sergey Pupyrev University of Arizona, USA Helen Purchase University of Glasgow, UK Marcus Schaefer DePaul University, USA VIII Organization Gerik Scheuermann Leipzig University, Germany Darren Strash Hamilton College, USA Shigeo Takahashi University of Aizu, Japan Tatiana von Landesberger Technische Universität Darmstadt, Germany Sue Whitesides University of Victoria, Canada David R. Wood Monash University, Australia Hsu-Chun Yen National Taiwan University, Taiwan Organizing Committee Vera Sacristán Universitat Politècnica de Catalunya, Spain Rodrigo Silveira Universitat Politècnica de Catalunya, Spain Contest Committee Will Devanny University of California at Irvine, USA Philipp Kindermann University of Waterloo, Canada Maarten Löffler (Chair) Utrecht University, The Netherlands Ignaz Rutter Universität Passau, Germany External Referees Ackerman, Eyal Didimo, Walter Kaufmann, Michael Aichem, Michael Dujmović, Vida Keil, Mark Akitaya, Hugo Döring, Hanna Keszegh, Balázs Alam, Jawaherul Evans, William Kieffer, Steve Arroyo, Alan Fink, Martin Kindermann, Philipp Balko, Martin Firman, Oksana Klemz, Boris Ballweg, Kathrin Frati, Fabrizio Klimenta, Mirza Barth, Lukas Förster, Henry Knauer, Kolja Bekos, Michael Grilli, Luca Kryven, Myroslav Bereg, Sergey Gronemann, Martin Kurz, Denis Biniaz, Ahmad Gupta, Siddharth Kynčl, Jan Blaszczyszyn, Bartek Hassoumi, Almoctar Lau, Lap Chi Bläsius, Thomas Healy, Patrick Lin, Chun-Cheng Brandenburg, Franz Hossain, Md. Iqbal Lu, Hsueh-I Chang, Hsien-Chih Hu, Yifan Lubiw, Anna Chimani, Markus Irvine, Veronika Löffler, Andre Cornelsen, Sabine Jaeger, Sabrina Mehrabi, Saeed Da Lozzo, Giordano Jesus Lobo, Maria Michael, Traoré Di Giacomo, Emilio Joret, Gwenaël Montecchiani, Fabrizio Organization IX Nöllenburg, Martin Rüegg, Ulf Wang, Yunhai Otachi, Yota Schulz, André Wiechert, Veit Patakova, Zuzana Sommer, Björn Wild, Pascal Pálvölgyi, Dömötör Tappini, Alessandra Wolff, Alexander Rahman, Md. Saidur Uehara, Ryuhei Wunderlich, Marcel Roselli, Vincenzo van Renssen, André Wybrow, Michael Rutter, Ignaz Wallner, Günter Yu, Tian-Li Rzążewski, Paweł Wang, Hung-Lung Zink, Johannes Sponsors Gold Sponsors Silver Sponsor Bronze Sponsor