Patrizio Angelini Reinhard von Hanxleden (Eds.) 4 6 7 3 Graph Drawing 1 S C and Network Visualization N L 30th International Symposium, GD 2022 Tokyo, Japan, September 13–16, 2022 Revised Selected Papers Lecture Notes in Computer Science 13764 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 Moti Yung Columbia University, New York, NY, USA More information about this series at https://link.springer.com/bookseries/558 Patrizio Angelini Reinhard von Hanxleden (Eds.) (cid:129) Graph Drawing and Network Visualization 30th International Symposium, GD 2022 – Tokyo, Japan, September 13 16, 2022 Revised Selected Papers 123 Editors Patrizio Angelini Reinhard vonHanxleden JohnCabotUniversity Kiel University Rome, Italy Kiel, Germany ISSN 0302-9743 ISSN 1611-3349 (electronic) Lecture Notesin Computer Science ISBN 978-3-031-22202-3 ISBN978-3-031-22203-0 (eBook) https://doi.org/10.1007/978-3-031-22203-0 ©TheEditor(s)(ifapplicable)andTheAuthor(s),underexclusivelicense toSpringerNatureSwitzerlandAG2023 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, 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 2022, the 30th International Sym- posium on Graph Drawing and Network Visualization, held during September 13–16, 2022 in Tokyo, Japan. Graph drawing is concerned with the geometric representation ofgraphsandconstitutesthealgorithmiccoreofnetworkvisualization.Graphdrawing 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. AswithGD2020andGD2021,this2022conferencewasheldunderextraordinary circumstances. After the GD 2020 conference, which sadly had to be held wholly online due to the COVID-19 pandemic, and GD 2021, which took place as a hybrid conference at Universität Tübingen, we had another hybrid conference at the Tokyo Institute of Technology. The credit for this remarkable achievement in such uncertain times goes wholly to the local organizers. A total of 29 participants from ten different countries attended the conference in person, with a further 115 registered participants from 17 countries online. Withregardstotheprogramitself,regularpaperscouldbesubmittedtooneoftwo distinct tracks: Track 1 for papers on combinatorial and algorithmic aspects of graph drawing and Track 2 for papers on experimental, applied, and network visualization aspects.Shortpapersweregivenaseparatecategory,whichwelcomedboththeoretical and applied contributions. An additional track was devoted to poster submissions. All the tracks were handled by a single Program Committee. As committed to during the GD 2021 business meeting, particular attention was given to the design of Track 2. Broadly speaking, Track 2 should serve as platform that links the theory with the practiceofgraphdrawing,andisseenasvitalcomponentfortheoverallrelevanceand further development of the community. Aiming for that goal prompted fairly deep discussions involving the current and former Program Chairs and the Steering Com- mittee and resulted in a slightly revised track description in the Call for Papers (CfP). As in previous editions of GD, the papers in the different tracks did not compete with each other, but all Program Committee members were invited to review papers from either track. In response tothe CfP, theProgram Committee received a totalof 70 submissions, consisting of 65 papers (32 in Track 1, 16 in Track 2, and 17 in the short paper category) and five posters. As a novelty for GD, the review process switched from a single-blind to a “lightweight double-blind” process, where authors were asked to not disclosetheiridentitiesbutwerefreetodisseminatedraftversionsofthepaperpriorto the conference and to give talks on the topic as they normally would. More than 210 reviews were provided, about a third having been contributed by external sub-reviewers. After extensive electronic discussions by the Program Com- mittee via EasyChair, interspersed with virtual meetings of the Program Chairs pro- ducingincrementalaccept/rejectproposals,25longpapers,sevenshortpapers,andfive vi Preface posterswereselectedforinclusioninthescientificprogramofGD2022.Thisresulted in an overall paper acceptance rate (not considering posters) of 49% (53% in Track 1, 50%inTrack2,and41%intheshortpapercategory).AsiscommoninGD,somehard choiceshadtobemade,inparticularduringthefinalacceptance/rejectionround,where several papers that clearly had merit still did not make it. However, the number of submittedhigh-qualitypapersspeaksforthecommunity,andwewerealsopleasedthat Track 2 ended up well-represented. Intotal,20ofthe34oralpresentations(includingtwoinvitedtalks)weredelivered on-site; the remaining 14 were delivered remotely using Zoom. Two posters were displayed on-site, all posters were also presented in Zoom breakout rooms. AuthorspublishedanelectronicversionoftheiracceptedpapersonthearXive-print repository; a conference index with links to these contributions was made available before the conference. There were two invited lectures at GD 2022. Ulrik Brandes from ETH Zürich (Switzerland) discussed “Positions in Social and Other Spaces”, while Kazuo Misue from the University of Tsukuba (Japan) talked about “Graph Drawing for Thinking Support.” Abstracts of both invited lectures are included in these proceedings. TheconferencegaveoutbestpaperawardsinTrack1andTrack2,aswellasabest presentation award and a best poster award. The award for the best paper in Track 1 wasgivento“Unavoidablepatternsincompletesimpletopologicalgraphs”byAndrew Suk and Ji Zeng, and the award for the best paper in Track 2 was assigned to “FORBID:FastOverlapRemovalByStochasticGradientDescentforGraphDrawing” byLoannGiovannangeli,FrédéricLalanne,RomainGiot,andRomainBourqui.Based onamajorityvoteofconferenceparticipants,thebestpresentationawardwasgivento Philipp Kindermann for his presentation of the paper “Morphing Rectangular Duals.” Therewasatieforthebestposteraward,whichwasgivento“TheWitnessUnitDisk Representability Problem” by Giuseppe Liotta, Maarten Löffler, Fabrizio Montecchi- ani, Alessandra Tappini, and Soeren Terziadis and to “Edge Bundling by Density-based Pathfinding Approach” by Ryosuke Saga, Tomoki Yoshikawa, and Tomoharu Nakashima. Many thanks to Springer whose sponsorship funded the prize money for these awards. A PhD School was held on the two days prior to the conference. Three half-day sessions led by six invited lecturers covered both theoretical and practical topics in graph drawing and network visualization. As is traditional, the 30th Annual Graph Drawing Contest was held during the conference. The contest was divided into two parts, creative topics and the live chal- lenge. The creative topics task featured two graphs, an Opera Network (the data rep- resented a collection of opera performances that took place across Europe between 1775 and 1833) and an Aesthetic Experience Network (the data set represented eight networksthatmodelanaestheticexperienceoftheviewerswhenobservingartworks). The live challenge focused on minimizing the planar polyline edge-length ratio on a fixed grid, with planar undirected inputs. There were two categories: manual and automatic. We thank the Contest Committee, chaired by Philipp Kindermann, for preparing interesting and challenging contest problems. A report about the contest is included in these proceedings. Preface vii Many people and organizations contributed to the success of GD 2022. 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 2022 as the publication venue for their research. We are grateful for the support of our “Gold” sponsor Tom Sawyer Software, our “Silver” sponsor yWorks, and our “Bronze” sponsor Springer. Our special thanks go to all the members of the organizing committee based at Ochanomizu University, Tokyo Institute of Technology, Hokkaido Information University, St. Polten University of Applied Sciences, IBM Research, Japan, and the National Institute of Advanced Industrial Science and Technology (AIST), Japan. The 31st International Symposium on Graph Drawing and Network Visualization (GD 2023) will take place during September 20–22, 2023, in Palermo, Italy. Michael Bekos and Markus Chimani will co-chair the Program Committee, and Emilio Di Giacomo,FabrizioMontecchiani,andAlessandraTappiniwillco-chairtheOrganizing Committee. October 2022 Patrizio Angelini Reinhard von Hanxleden Organization Steering Committee Patrizio Angelini John Cabot University, Italy Michael A. Bekos University of Ioannina, Greece Markus Chimani Osnabrück University, Germany Giuseppe Di Battista Roma Tre University, Italy Emilio Di Giacomo University of Perugia, Italy Reinhard von Hanxleden University of Kiel, Germany Stephen G. Kobourov University of Arizona, USA (Chair) Anna Lubiw University of Waterloo, Canada Helen Purchase Monash University, Australia Ignaz Rutter University of Passau, Germany Roberto Tamassia Brown University, USA Ioannis G. Tollis ICS-FORTH and University of Crete, Greece Alexander Wolff University of Würzburg, Germany Program Committee Patrizio Angelini (Co-chair) John Cabot University, Italy Therese Biedl University of Waterloo, Canada Sabine Cornelsen University of Konstanz, Germany Giordano Da Lozzo Roma Tre University, Italy Stephan Diehl University of Trier, Germany Henry Förster Universität Tübingen, Germany Martin Gronemann TU Wien, Austria Yasuhiro Hashimoto University of Aizu, Japan Michael Hoffmann ETH Zurich, Switzerland Hiroshi Hosobe Hosei University, Japan Yifan Hu Yahoo!, USA Takayuki Itoh Ochanomizu University, Japan Philipp Kindermann Universität Trier, Germany Karsten Klein University of Konstanz, Germany Stephen Kobourov University of Arizona, USA Jan Kratochvil Charles University, Czech Republic Kim Marriott Monash University, Australia Irene Parada DTU, Denmark Sergey Pupyrev University of Arizona, USA Helen Purchase Monash University, Australia Arnaud Sallaberry LIRMM, Université Paul-Valéry Montpellier 3, Université de Montpellier, CNRS, France x Organization Ingo Scholtes University of Zurich, Switzerland Falk Schreiber University of Konstanz, Germany André Schulz FernUniversität in Hagen, Germany Andrew Suk University of California, San Diego, USA Antonios Symvonis National Technical University of Athens, Greece Alessandra Tappini University of Perugia, Italy Reinhard von Hanxleden Christian-Albrechts-Universität zu Kiel, Germany (Co-chair) Tatiana von Landesberger University of Cologne, Germany Meirav Zehavi Ben-Gurion University, Israel Organizing Committee Takayuki Itoh (Chair) Ochanomizu University, Japan Ken Wakita Tokyo Institute of Technology, Japan Masahiko Itoh Hokkaido Information University, Japan Hsiang-Yun Wu St. Pölten University of Applied Sciences, Austria Rina Nakazawa IBM Research, Japan Yuri Miyagi National Institute of Advanced Industrial Science and Technology (AIST), Japan Contest Committee Philipp Kindermann (Chair) University of Trier, Germany Fabian Klute Utrecht University, The Netherlands Tamara Mchedlidze Utrecht University, The Netherlands Wouter Meulemans TU Eindhoven, The Netherlands External Reviewers Ahmed, Abu Reyan Giovannangeli, Loann Aichholzer, Oswin Grilli, Luca Alegría, Carlos Grosso, Fabrizio Archambault, Daniel Karim, Md. Rezaul Bläsius, Thomas Keszegh, Balázs Chen, Kun-Ting Kryven, Myroslav Crnovrsanin, Tarik Kuckuk, Axel Di Bartolomeo, Sara Lahiri, Abhiruk Di Giacomo, Emilio Li, Guangping Didimo, Walter Löffler, Maarten Durocher, Stephane Martins, Rafael M. Eppstein, David Meulemans, Wouter Felsner, Stefan Miltzow, Till Fink, Simon D. Montecchiani, Fabrizio Frati, Fabrizio Morin, Pat