Seok-Hee Hong Takeshi Tokuyama Eds. Beyond Planar Graphs Communications of NII Shonan Meetings Beyond Planar Graphs Seok-Hee Hong Takeshi Tokuyama (cid:129) Editors Beyond Planar Graphs Communications of NII Shonan Meetings 123 Editors Seok-HeeHong Takeshi Tokuyama Schoolof Computer Science Schoolof Science andTechnology University of Sydney Kwansei Gakuin University Sydney,NSW,Australia Sanda,Hyogo,Japan ISBN978-981-15-6532-8 ISBN978-981-15-6533-5 (eBook) https://doi.org/10.1007/978-981-15-6533-5 ©SpringerNatureSingaporePteLtd.2020 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpart of the 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 orinformationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodologynowknownorhereafterdeveloped. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfrom therelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained hereinorforanyerrorsoromissionsthatmayhavebeenmade.Thepublisherremainsneutralwithregard tojurisdictionalclaimsinpublishedmapsandinstitutionalaffiliations. ThisSpringerimprintispublishedbytheregisteredcompanySpringerNatureSingaporePteLtd. The registered company address is: 152 Beach Road, #21-01/04 Gateway East, Singapore 189721, Singapore Preface Mostreal-worlddatasetsarerelational,whichcanbemodeledasgraphs,consisting of vertices and edges. Planar graphs are fundamental for both Graph Theory and Graph Algorithms, and extensively studied: structural properties and fundamental algorithms for planar graphs have been discovered. However, most real-world graphs, such as social networks and biological networks, are non-planar. To ana- lyze and visualize such real-world networks, we need to solve fundamental math- ematical and algorithmic research questions on sparse non-planar graphs, called beyond planar graphs. Recently, research topics in topological graph theory generalize the notion of planarity to beyond-planar graphs, i.e., non-planar graphs with topological con- straints such as specific types of crossings, or with forbidden crossing patterns. Examples include: (cid:129) k-planar graphs, which can be embedded with at most k crossings per edge; (cid:129) k-quasi-planar graphs, which can be embedded without k mutually crossing edges. Consequently, combinatorics (such as edge density), algorithmics (such as testing/embeddingalgorithms),andgeometricrepresentations(suchasstraight-line drawings) of beyond-planar graphs have emerged as new research directions. The NII (National Institute of Informatics) Shonan Meeting No-089 Algorithmics on Beyond Planar Graphs was held on November 27–December 1, 2016 in Shonan, Japan, to bring world-renowned researchers on Graph Algorithm, Graph Drawing, Computational Geometry, Graph Theory, and Combinatorial Optimization. ThemainaimoftheworkshopwastoidentifyresearchopportunitiesonBeyond Planar Graphs and collaboratively develop innovative theory and algorithms for sparse non-planar topological graphs with specific applications to large and com- plex network visualization. The workshop had 26 participants from 7 countries, and consisted of 7 invited talks, open problem sessions, discussion sessions, and report sessions from each working group. Outcomes of the workshop include the Shonan Meeting Report, v vi Preface research articles as well as invited contributions to the book chapters from the participants. This book contains a selection of book chapters initiated from the Shonan Workshop No-089 on Beyond Planar Graphs. More specifically, it consists of 13 chapters that represent recent advances in various areas of beyond planar graph research. Each book chapter was peer-reviewed according to the book standards. The main aims and objectives of this book include: (cid:129) timely provide the state-of-the-art survey and a bibliography on beyond planar graphs; (cid:129) set the research agenda on beyond planar graphs by identifying fundamental research questions and new research directions; (cid:129) foster cross-disciplinary research collaboration between Computer Science (Graph Drawing and Computational Geometry) and Mathematics (Graph Theory and Combinatorics). This book is the first general and extensive review of the algorithmic and mathematical results of beyond planar graphs. New algorithms for beyond planar graphs will be in high demand by practitioners in various application domains to solve complex visualization problems. As such, this book will be a valuable resource for researchers in Graph theory, Algorithms, and Theoretical Computer Science,andwillstimulatefurtherdeepscientificinvestigationsintomanyareasof beyond planar graphs. Wewishtothankalltheauthorsforcontributingtheirchapterstothisbook.We also thank all the participants of the Shonan Workshop No-089 for their valuable contribution and participation during the workshop, which greatly helped to improve many aspects of the chapters published in this book. Finally,we wouldlike tothank NII fortheopportunitytoorganizeasuccessful meetingtoenabletheseexcitinginitiatives,andSpringerfortheopportunitytoedit this book, with dedicated assistance and support to make this book possible. Sydney, Australia Seok-Hee Hong Sanda, Japan Takeshi Tokuyama March, 2020 Contents 1 Beyond Planar Graphs: Introduction . . . . . . . . . . . . . . . . . . . . . . . 1 Seok-Hee Hong 2 Quantitative Restrictions on Crossing Patterns. . . . . . . . . . . . . . . . 11 Csaba D. Tóth 3 Quasi-planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Eyal Ackerman 4 1-Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 Yusuke Suzuki 5 Algorithms for 1-Planar Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Seok-Hee Hong 6 Edge Partitions and Visibility Representations of 1-planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Giuseppe Liotta and Fabrizio Montecchiani 7 k-Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Michael A. Bekos 8 Fan-Planar Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 Michael A. Bekos and Luca Grilli 9 Right Angle Crossing Drawings of Graphs. . . . . . . . . . . . . . . . . . . 149 Walter Didimo 10 Angular Resolutions: Around Vertices and Crossings. . . . . . . . . . . 171 Yoshio Okamoto 11 Crossing Layout in Non-planar Graph Drawings. . . . . . . . . . . . . . 187 Martin Nöllenburg vii viii Contents 12 Beyond Clustered Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 211 Patrizio Angelini and Giordano Da Lozzo 13 Simultaneous Embedding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 Ignaz Rutter Index .... .... .... .... .... ..... .... .... .... .... .... ..... .... 267 Chapter 1 Beyond Planar Graphs: Introduction Seok-HeeHong Abstract Recent research topics in topological graph theory and graph drawing generalize the notion of planarity to sparse non-planar graphs called beyond pla- nar graphs with forbidden crossing patterns. In this chapter, we introduce various typesofbeyondplanargraphsandbrieflyreviewknownresultsontheedgedensity, computationalcomplexity,andalgorithmsfortestingbeyondplanargraphs. 1.1 BeyondPlanarGraphs:EdgeDensity Recent research topics in topological graph theory and graph drawing generalize the notion of planarity to sparse non-planar graphs, called beyond planar graphs, eitherwithforbiddenedgecrossingpatternsorwithspecifictypesofedgecrossings. Examplesinclude: • k-planar graphs: graphs which can be embedded with at most k crossings per edge[40]. • k-quasi-planargraphs:graphswhichcanbeembeddedwithoutkmutuallycross- ingedges[2]. • RACgraphs:graphswhichcanbeembeddedwithrightanglecrossings[19]. • fan-crossing-free graphs: graphs which can be embedded without fan- crossings[17]. • fan-planargraphs:graphswhichcanbeembeddedsuchthateachedgeiscrossed byabundleofedgesincidenttoacommonvertex[35]. • k-gap-planargraphs:graphswhichcanbeembeddedsuchthateachcrossingis assignedtooneofthetwoinvolvededgesandeachedgeisassignedatmostk of itscrossings. Figure1.1 shows examples of forbidden crossing patterns for beyond planar graphs. B S.-H.Hong( ) UniversityofSydney,Sydney,Australia e-mail:[email protected] ©SpringerNatureSingaporePteLtd.2020 1 S.-H.HongandT.Tokuyama(eds.),BeyondPlanarGraphs, https://doi.org/10.1007/978-981-15-6533-5_1 2 S.-H.Hong Fig. 1.1 Examples of crossing patterns: a fan-crossing (fan-planar and 2-planar graph, but not fan-crossing-freegraph);b3mutuallycrossingedges(notquasi-planargraph);cfan-crossing-free and2-planargraph(butnotfan-planar);dRACand2-planargraph Combinatorialaspectsofbeyondplanargraphsarewellstudied,forexample,the maximumnumberofedgesofbeyondplanargraphs: • k-planargraphs:PachandToth[40]provedthat1-planargraphswithn vertices haveatmost4n−8edges. • k-quasi-planargraphs:Agarwaletal.[2](respectively,Ackerman[1])provedthat 3(respectively,4)-quasi-planargraphshavelinearnumberofedges.Foxetal.[26] showedthatk-quasi-planargraphshaveatmost O(nlog1+o(1)n)edges. • RAC graphs: Didimo et al. [19] proved that RAC graphs have at most 4n−10 edges. • fan-crossing-freegraphs:Cheongetal.[17]provedatightboundof4n−8onthe maximumnumberofedgesfora2-fan-crossing-freegraph,andanupperbound of3(k−1)(n−2)edgesfork ≥3. • fan-planar graphs: Kaufmann and Ueckerdt [35] showed that fan-planar graphs haveatmost5n−10edges. • k-g√ap-planar graphs: Bae et al. [7] proved that every k-gap-planar graph has O( kn) edges (for k = 1, an upper bound is 5n−10). They also study rela- tionshipstootherclassesofbeyondplanargraphs. Wenowbrieflyreviewlatestresultsonbeyondplanargraphs,mainlyfocusingon thecomputationalcomplexityandalgorithmicaspects. 1.2 ComputationalComplexity:NP-Hardness Recently,computationalcomplexityfortestingbeyondplanarityhasbeenstudied. Morespecifically: • 1-planar graphs: Grigoriev and Bodlaender [29], and Korzhik and Mohar [37] independentlyprovedthattesting1-planarityofagraphisNP-complete.Aueret al.[6].showedthatitremainsNP-hard,evenifarotationsystem(i.e.,thecircular orderingofedgesforeachvertex)isgiven.