Graph Drawing and Network Visualization: 31st International Symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20–22, 2023, Revised Selected Papers 2

This two-volume set LNCS 14465-14466 constitutes the proceedings of the 31st International Symposium on Graph Drawing and Network Visualization, GD 2023, held in Isola delle Femmine, Palermo, Italy, in September 2023. The 31 full papers, 7 short papers, presented together with 2 invited talks, and one contest report, were thoroughly reviewed and selected from the 100 submissions. The abstracts of 11 posters presented at the conference can be found in the back matter of the volume. The contributions were organized in topical sections as follows: beyond planarity; crossing numbers; linear layouts; geometric aspects; visualization challenges; graph representations; graph decompositions; topological aspects; parameterized complexity for drawings; planar graphs; frameworks; algorithmics. Preface Organization Invited Talks The CGAL Project – cgal.org On Orthogonal Drawings of Plane and Not So Plane Graphs Contents – Part II Contents – Part I Topological Aspects Cops and Robbers on 1-Planar Graphs 1 Introduction 2 1-Planar Graphs May Have Unbounded Cop Number 3 Cop Number of Quadrangulations 4 Cop Number of Maximal 1-Planar Graphs 4.1 Lower Bound 4.2 Upper Bound 5 Characterization of Cop-Win Outer 1-Planar Graphs 6 Discussion and Directions for Future Research References Removing Popular Faces in Curve Arrangements 1 Introduction 1.1 Results 2 Resolving One popular Face by Adding a Single Curve 3 N1R is NP-complete 3.1 Non-intersecting Eulerian Cycles 3.2 NP-completeness Reduction 4 Randomized FPT-algorithm for N1R 4.1 Computing Sums of Path Weights by Dynamic Programming 4.2 Runtime and Space 5 Conclusion References Different Types of Isomorphisms of Drawings of Complete Multipartite Graphs 1 Introduction 1.1 Obtained Results 2 Drawings of General Complete Multipartite Graphs 3 Drawings of Complete Multipartite Graphs Where Each Partition Class Contains at Least Three Vertices 4 Examples of Simple Drawings Showing Specific Properties 5 Conclusion References Parameterized Complexity for Drawings On the Parameterized Complexity of Bend-Minimum Orthogonal Planarity 1 Introduction 2 Preliminaries 3 The Biconnected Case 4 The General Case References Fixed-Parameter Algorithms for Computing RAC Drawings of Graphs 1 Introduction 2 Preliminaries 3 An Explicit Algorithm for BRAC 4 A Fixed-Parameter Algorithm via fen(G) 5 Fixed-Parameter Tractability via vcn(G) 6 Concluding Remarks References Parameterized Complexity of Simultaneous Planarity 1 Introduction 2 Preliminaries 3 Parameters of the Union Graph 3.1 Vertex Cover Number 3.2 Feedback Edge Set Number 3.3 Twin Cover Number 4 Parameters of the Shared Graph 4.1 Maximum Degree 4.2 Vertex Cover Number + Maximum Degree-1 Neighbors 4.3 Number of Cutvertices + Maximum Degree 5 Conclusion References The Parametrized Complexity of the Segment Number 1 Introduction 2 Preliminaries 3 The Segment Number of Banana Trees and Cycles 4 Parameter: Vertex Cover Number 5 Parameters: Segment and Line Cover Number 6 Open Problems References Planar Graphs A Schnyder-Type Drawing Algorithm for 5-Connected Triangulations 1 Introduction 2 Schnyder Structures for Triangulations of the Pentagon 2.1 Definitions About Triangulations 2.2 Three Incarnations of Schnyder Structures on 5-Triangulations 2.3 Existence and Computation of Schnyder Structures 3 Graph Drawing Algorithm for 5c-Triangulations 3.1 Paths and Regions 3.2 Graph Drawing Algorithm 3.3 Proof of Planarity 3.4 Variations and Other Properties References A Logarithmic Bound for Simultaneous Embeddings of Planar Graphs 1 Introduction 2 Order Types and Straight-Line Embeddings 3 Proof of Theorem 1 4 Conclusive Remarks References Manipulating Weights to Improve Stress-Graph Drawings of 3-Connected Planar Graphs 1 Introduction 2 Algorithms 3 Experiments References Frameworks Computing Hive Plots: A Combinatorial Framework 1 Introduction 2 Formal Model 3 Framework for Computing Hive Plots 3.1 Vertex Partitioning 3.2 Axis Ordering 3.3 Crossing Minimization 4 Implementation and Hive Plot Rendering 5 Case Study 6 Computational Experiments 7 Discussion and Conclusion References A Simple Pipeline for Orthogonal Graph Drawing 1 Introduction 2 Our Pipeline 3 Experiments 4 Conclusions References Algorithmics Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem 1 Introduction 2 Definitions and Terminology 3 FPT Algorithms for MWBS by Branchwidth 4 Compression for MWBS by b 5 Efficient PTAS for MWBS and Final Remarks References Upward and Orthogonal Planarity are W[1]-Hard Parameterized by Treewidth 1 Introduction 2 Preliminaries 3 Overview 3.1 Hardness of All-or-Nothing-Flow 3.2 Hardness of Circulating Orientation 3.3 From Circulating Orientation to Planarity Testing Problems 4 Conclusion References On Minimizing the Energy of a Spherical Graph Representation 1 Introduction 2 Upper Bound 3 The Semidefinite Program 4 Semidefinite Representations and Eigenvector Representations 5 Random Regular Graphs 5.1 High Girth 5.2 Random Graphs References Posters One-Bend Drawing of Kn in 3D, Revisited References Accurate and Simple Metaphoric Maps References Quantum Tutte Embeddings 1 Introduction References The Widths of Strict Outerconfluent Graphs References Convex-Geometric k-Planar Graphs Are Convex-Geometric (k+1)-Quasiplanar 1 Contribution References A Collection of Benchmark Datasets for Evaluating Graph Layout Algorithms Editing Graph Visualizations by Prompting Large Language Models 1 Introduction 2 Approach References On Layered Area-Proportional Rectangle Contact Representations References odgf-python – A Python Interface for the Open Graph Drawing Framework References Drawing Reeb Graphs 1 Introduction References What Happens at Dagstuhl? Uncovering Patterns Through Visualization 1 Introduction 2 The Visualization System References Author Index