Daniel Archambault Csaba D. Tóth (Eds.) 4 0 9 1 Graph Drawing 1 S C and Network Visualization N L 27th International Symposium, GD 2019 Prague, Czech Republic, September 17–20, 2019 Proceedings Lecture Notes in Computer Science 11904 Founding Editors Gerhard Goos Karlsruhe Institute of Technology, Karlsruhe, Germany Juris Hartmanis Cornell University, Ithaca, NY, USA Editorial Board Members Elisa Bertino Purdue University, West Lafayette, IN, USA Wen Gao Peking University, Beijing, China Bernhard Steffen TU Dortmund University, Dortmund, Germany Gerhard Woeginger RWTH Aachen, Aachen, Germany Moti Yung Columbia University, New York, NY, USA More information about this series at http://www.springer.com/series/7407 ó Daniel Archambault Csaba D. T th (Eds.) (cid:129) Graph Drawing and Network Visualization 27th International Symposium, GD 2019 – Prague, Czech Republic, September 17 20, 2019 Proceedings 123 Editors DanielArchambault CsabaD.Tóth SwanseaUniversity California State University, Northridge Swansea, UK LosAngeles, CA, USA ISSN 0302-9743 ISSN 1611-3349 (electronic) Lecture Notesin Computer Science ISBN 978-3-030-35801-3 ISBN978-3-030-35802-0 (eBook) https://doi.org/10.1007/978-3-030-35802-0 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ©SpringerNatureSwitzerlandAG2019 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,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbookare believedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsortheeditors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissionsthatmayhavebeenmade.Thepublisherremainsneutralwithregardtojurisdictionalclaimsin publishedmapsandinstitutionalaffiliations. ThisSpringerimprintispublishedbytheregisteredcompanySpringerNatureSwitzerlandAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Preface This volume contains the papers presented at GD 2019, the 27th International Symposium on Graph Drawing and Network Visualization, held during September 17–20, 2019, in Průhonice, near Prague. Graph drawing is concerned with thegeometricrepresentation ofgraphs andconstitutesthealgorithmic coreofnetwork visualization. Graph drawing and network visualization are motivated by applications whereitiscrucialtovisuallyanalyzeandinteractwithrelationaldatasets.Information about the conference series and past symposia is maintained at http://www. graphdrawing.org. The 2019 edition of the conference was hosted by the Charles University, with Jiří Fiala and Pavel Valtr as co-chairs of the Organizing Committee. A total of 98 participants attended the conference. Regularpaperscouldbesubmitted tooneoftwodistinct tracks:Track1forpapers on combinatorial and algorithmic aspects of graph drawing or 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 additionaltrackwasdevotedtopostersubmissions.Alltrackswerehandledbyasingle Program Committee. In response to the call for papers, the Program Committee received a total of 113 submissions, consisting of 100 papers (56 in Track 1, 25 in Track2,and19intheshortpapercategory)and13posters.Morethan350single-blind reviews were provided, more than a third of which were contributed by external sub-reviewers. After extensive electronic discussions via EasyChair, the Program Committeeselected42papersand12postersforinclusioninthescientificprogramof GD 2019. This resulted in an overall paper acceptance rate of 42% (45% in Track 1, 36%inTrack2,and42%intheshortpapercategory).Authorspublishedanelectronic version of their accepted papers on the arXiv e-print repository; a conference index with links to these contributions was made available before the conference. There were three invited lectures at GD 2019, one on each day of the scientific program. John T. Stasko, from the Georgia Institute of Technology, USA, presented “PushingtheBoundaries ofInteractioninDataVisualization,”BartoszWalczak,from theJagiellonianUniversity,Poland,talkedabout“OldandNewChallengesinColoring Graphs with Geometric Representations,” and Giuseppe Di Battista, from the Università Roma Tre, Italy, made the case that “This is Time in/for Graph Drawing.” Abstracts of all three invited lectures are included in these proceedings. TheconferencegaveoutbestpaperawardsinTrack1andTrack2,aswellasabest presentation award and a best poster award. As decided by a majority vote of the Program Committee, the award for the best paper in Track 1 was assigned to “Exact Crossing Number Parameterized by Vertex Cover” by Petr Hlinĕný and Abhisekh Sankaran, and the award for the best paper in Track 2 was assigned to “Symmetry Detection and Classification in Drawings of Graphs” by Felice De Luca, Md. Iqbal Hossain, and Stephen Kobourov. Based on a majority vote of conference participants, the best presentation award was given to Arthur van Goethem for his presentation vi Preface of the paper “Optimal Morphs of Planar Orthogonal Drawings II,” and the best poster awardwasgivento“PackingTreesinto1-planarGraphs”byFeliceDeLuca,EmilioDi Giacomo, Seok-Hee Hong, Stephen Kobourov, William Lenhart, Giuseppe Liotta, Henk Meijer, Alessandra Tappini, and Stephen Wismath. Congratulations to all the award winners for their excellent contributions, and many thanks to Springer whose sponsorship funded the prize money for these awards. Following the tradition, the 26th 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, the Marvel Cinematic Universe graph and the Meal Ingredients graph. The live challenge focused on minimizing the number of crossings in an upward drawing on a fixed grid, and had two categories: manualandautomatic.Awardsweregivenineachofthefourcategories.Wethankthe Contest Committee, chaired by Philipp Kindermann, for preparing interesting and challenging contest problems. A report about the contest is included in these proceedings. Many people and organizations contributed to the success of GD 2019. We would like to thank all members of the Program Committee and the external reviewers for carefully reviewing and discussing the submitted papers and posters; this was crucial forputtingtogetherastrongandinterestingprogram.Thankstoallauthorswhochose GD 2019 as the publication venue for their research. We are grateful for the support of the “gold” sponsors Avast, RSJ, Tom Sawyer Software, Unicorn, and yWorks, the “bronze” sponsor Springer, and contributor Znovín Znojmo. Their generosity helped make this symposium a memorable event for all participants. Last but not least, we would like to express our appreciation of the organizing team: all members of the Organizing Committee, Martin Balko, Jiří Fiala, Anna Kotĕšovcová, and Pavel Valtr, as well as all student volunteers, Jaroslav Hančl, Radek Hušek, Tomáš Masařík, Jana Novotná, Michael Skotnica, Jana Syrovátková, Aneta Št’astná, and Peter Zeman. The 28th International Symposium on Graph Drawing and Network Visualization (GD2020)willtakeplaceduringSeptember16–18,2020,inVancouver,BC,Canada. David Auber and Pavel Valtr will co-chair the Program Committee, and Will Evans will chair the Organizing Committee. October 2019 Daniel Archambault Csaba D. Tóth Organization Steering Committee Daniel Archambault Swansea University, UK David Auber LaBRI, Université Bordeaux I, France Therese Biedl University of Waterloo, Canada Giuseppe Di Battista Università Roma Tre, Italy Walter Didimo University of Perugia, Italy Andreas Kerren Linnaeus University, Sweden Stephen G. Kobourov University of Arizona, USA (Chair) Martin Nöllenburg Technische Universität Wien, Austria Roberto Tamassia Brown University, USA Ioannis G. Tollis University of Crete, Greece, and Tom Sawyer Software, USA Csaba D. Tóth California State University, Northridge, USA Pavel Valtr Charles University, Czech Republic Program Committee Daniel Archambault Swansea University, UK (Co-chair) David Auber LaBRI, Université Bordeaux 1, France Benjamin Bach The University of Edinburgh, UK Fabian Beck University of Duisburg-Essen, Germany Michael Bekos University of Tübingen, Germany Prosenjit Bose Carleton University, Canada Maike Buchin Ruhr University Bochum, Germany Nan Cao Tongji University, China Giordano Da Lozzo Università Roma Tre, Italy Emilio Di Giacomo University of Perugia, Italy Tim Dwyer Monash University, Australia David Eppstein University of California, Irvine, USA Yifan Hu Yahoo! Research, USA Irina Kostitsyna TU Eindhoven, The Netherlands Jan Kynčl Charles University, Czech Republic Anna Lubiw University of Waterloo, Canada Maarten Löffler Utrecht University, The Netherlands Kwan-Liu Ma University of California, Davis, USA Silvia Miksch Technische Universität Wien, Austria Kazuo Misue University of Tsukuba, Japan Helen Purchase University of Glasgow, UK viii Organization Ignaz Rutter Universität Passau, Germany Alexandru Telea University of Groningen, The Netherlands Csaba D. Tóth (Co-chair) California State University, Northridge, USA Torsten Ueckerdt Karlsruhe Institute of Technology, Germany Birgit Vogtenhuber Graz University of Technology, Austria Hsiang-Yun Wu Technische Universität Wien, Austria Organizing Committee Martin Balko Charles University, Czech Republic Jiří Fiala (Co-chair) Charles University, Czech Republic Anna Kotĕšovcová Conforg Ltd, Czech Republic Pavel Valtr (Co-chair) Charles University, Czech Republic Contest Committee Philipp Kindermann (Chair) Universität Würzburg, Germany Tamara Mchedlidze Karlsruhe Institute of Technology, Germany Ignaz Rutter Universität Passau, Germany External Reviewers Ábrego, Bernardo Crnovrsanin, Tarik Ackerman, Eyal D’Angelo, Anthony Aerts, Nieke De Luca, Felice Aichholzer, Oswin Didimo, Walter Akopyan, Arseniy Dujmović, Vida Almeida Leite, Roger Felsner, Stefan Angelini, Patrizio Frati, Fabrizio Arroyo, Alan Fulek, Radoslav Balko, Martin van Garderen, Mereke Bhore, Sujoy Gonçalves, Daniel Biniaz, Ahmad Goodwin, Sarah Binucci, Carla Grastien, Ban Bläsius, Thomas Grelier, Nicolas Borrazzo, Manuel Grilli, Luca Brückner, Guido Gronemann, Martin Buchin, Kevin Gschwandtner, Theresia Bärtschi, Andreas Gupta, Siddharth Cano, Pilar Hidalgo-Toscano, Carlos Cardinal, Jean Hill, Darryl Carrière, Mathieu Hoffmann, Michael Chaplick, Steven van der Hoog, Ivor Chimani, Markus Isaacs, Kate Cibulka, Josef Itoh, Masahiko Cornelsen, Sabine Kaaser, Dominik Organization ix Kaufmann, Michael Ortali, Giacomo Keszegh, Balázs Palfrader, Peter Kilgus, Bernhard Parada, Irene Kindermann, Philipp Patrignani, Maurizio Kleist, Linda Pergel, Martin Klemz, Boris Pupyrev, Sergey Klute, Fabian Radermacher, Marcel van Kreveld, Marc Ravsky, Alexander Kriegel, Klaus van Renssen, André Kryven, Myroslav Roy, Sasanka Kwon, Oh-Hyun Ryvkin, Leonie Langerman, Stefan Sallaberry, Arnaud Lhuillier, Antoine Schetinger, Victor Li, Guangping Schnider, Patrick Maheshwari, Anil Schröder, Felix McGee, Fintan Schulz, André Micek, Piotr Selbach, Leonie Miltzow, Till Stumpf, Peter Mondal, Debajyoti T. P., Sandhya Montecchiani, Fabrizio Tappini, Alessandra Morin, Pat Tóth, Géza Mulzer, Wolfgang Verbeek, Kevin Mütze, Torsten Wakita, Ken Niedermann, Benjamin Wood, David R. Okamoto, Yoshio Wybrow, Michael Onoue, Yosuke