14 minute read

WEDNESDAY         
TIME (JST) ACTIVITY MIN AUTHORS  
09:00 - 09:30 Registration      
09:30 - 09:35 Opening      
Session 1     Chair: Emilio Di Giacomo  
09:35 - 09:55 Unavoidable patterns in complete simple topological graphs (best T1) 20 Andrew Suk and Ji Zeng  
09:55 - 10:10 Empty Triangles in Generalized Twisted Drawings of K_n 15 Alfredo Garcia, Javier Tejel, Birgit Vogtenhuber and Alexandra Weinberger  
10:10 - 10:25 Compatible Spanning Trees in Simple Drawings of $K_n$ 15 Rosna Paul, Oswin Aichholzer, Kristin Knorr, Birgit Vogtenhuber, Johannes Obenaus, Wolfgang Mulzer, Nicolas El Maalouly, Meghana M Reddy and Alexandra Weinberger  
10:25 - 10:40 Shooting Stars in Simple Drawings of K_{m,n} 15 Oswin Aichholzer, Alfredo Garcia, Irene Parada, Birgit Vogtenhuber and Alexandra Weinberger  
10:40 - 11:10 Break      
Session 2     Chair: Philipp Kindermann  
11:10 - 11:30 Small Point-Sets Supporting Graph Stories 20 Giuseppe Di Battista, Walter Didimo, Luca Grilli, Fabrizio Grosso, Giacomo Ortali, Maurizio Patrignani and Alessandra Tappini  
11:30 - 11:50 On the Complexity of the Storyplan Problem 20 Carla Binucci, Emilio Di Giacomo, William J. Lenhart, Giuseppe Liotta, Fabrizio Montecchiani, Martin Nöllenburg and Antonios Symvonis  
11:50 - 12:10 On Time and Space: An Experimental Study on Graph Structural and Temporal Representations 20 Velitchko Filipov, Alessio Arleo, Markus Bögl and Silvia Miksch  
12:10 - 12:30 Improved Scheduling of Morphing Edge Drawing 20 Kazuo Misue  
12:30 - 14:00 Lunch      
Session 3     Chair: Ken Wakita  
14:00 - 14:20 Quasiplanar graphs, string graphs, and the Erdős-Gallai problem 20 Jacob Fox, Janos Pach and Andrew Suk  
14:20 - 14:40 The thickness of fan-planar graphs is at most three 20 Otfried Cheong, Maximilian Pfister and Lena Schlipf  
14:40 - 15:00 Arrangements of Pseudocircles: On Digons and Triangles 20 Stefan Felsner, Sandro Roch and Manfred Scheucher  
15:00 - 15:20 Mutual Witness Gabriel Drawings of Complete Bipartite Graphs 20 William Lenhart and Giuseppe Liotta  
15:20 - 15:30 Poster pitches      
15:30 - 16:30 Break + poster      
16:30 - 18:00 Contest      


THURSDAY            
TIME (JST) ACTIVITY MIN AUTHORS  
09:00 - 09:30 Registration      
  Keynote I   Chair: Patrizio Angelini  
09:30 - 10:30 Positions in Social and Other Spaces 60 Ulrik Brandes  
10:30 - 11:00 Break      
Session 4     Chair: Jiaxi Nie  
11:00 - 11:20 Planarizing Graphs and their Drawings by Vertex Splitting 20 Soeren Nickel, Martin Nöllenburg, Manuel Sorge, Anaïs Villedieu, Hsiang-Yun Wu and Jules Wulms  
11:20 - 11:35 An FPT Algorithm for Bipartite Vertex Splitting 15 Reyan Ahmed, Stephen Kobourov and Myroslav Kryven  
11:35 - 11:50 Queue Layouts of Two-Dimensional Posets 15 Sergey Pupyrev  
11:50 - 12:10 The Rique-Number of Graphs 20 Michael Bekos, Stefan Felsner, Philipp Kindermann, Stephen Kobourov, Jan Kratochvíl and Ignaz Rutter  
12:10 - 12:25 Recognizing DAGs with Page-Number 2 is NP-complete 15 Michael Bekos, Giordano Da Lozzo, Fabrizio Frati, Martin Gronemann, Tamara Mchedlidze and Chrysanthi Raftopoulou  
12:30 - 14:00 Lunch      
Session 5 In Memoriam: Prof. Takao Nishizeki   Chair: Md. Saidur Rahman  
14:00 - 14:05 Obituary Prof. Nishizeki      
14:05 - 14:25 Strictly-Convex Drawings of 3-Connected Planar Graphs 20 Michael Bekos, Martin Gronemann, Fabrizio Montecchiani and Antonios Symvonis  
14:25 - 14:45 Rectilinear Planarity of Partial 2-Trees 20 Walter Didimo, Michael Kaufmann, Giuseppe Liotta and Giacomo Ortali  
14:45 - 15:05 Unit-length Rectangular Drawings of Graphs 20 Carlos Alegría, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Fabrizio Grosso and Maurizio Patrignani  
15:05 - 15:25 Planar Confluent Orthogonal Drawings of 4-Modal Digraphs 20 Sabine Cornelsen and Gregor Diatzko  
15:25 - 16:00 Break      
16:00 - 17:30 Business meeting      


FRIDAY                     
TIME (JST) ACTIVITY MIN AUTHORS  
09:00 - 09:30 Registration      
  Keynote I   Chair: Reinhard von Hanxleden  
09:30 - 10:30 Graph Drawing for Thinking Support 60 Kazuo Misue‬  
10:30 - 11:00 Break      
Session 6     Chair: Takayuki Itoh  
11:00 - 11:20 FORBID: Fast Overlap Removal By Stochastic Gradient Descent for Graph Drawing (best T2) 20 Loann Giovannangeli, Frédéric Lalanne, Romain Giot and Romain Bourqui  
11:20 - 11:40 Spherical Graph Drawing by Multidimensional Scaling 20 Jacob Miller, Vahan Huroyan and Stephen Kobourov  
11:40 - 12:00 Shape-Faithful Graph Drawings 20 Amyra Meidiana, Seok-Hee Hong and Peter Eades  
12:00 - 12:20 Visualizing Evolving Trees 20 Kathryn Gray, Mingwei Li, Abu Reyan Ahmed and Stephen Kobourov  
12:30 - 14:00 Lunch      
Session 7     Chair: Andrew Suk  
14:00 - 14:20 Morphing Rectangular Duals 20 Steven Chaplick, Philipp Kindermann, Jonathan Klawitter, Ignaz Rutter and Alexander Wolff  
14:20 - 14:40 Coloring Mixed and Directional Interval Graphs 20 Grzegorz Gutowski, Florian Mittelstädt, Ignaz Rutter, Joachim Spoerhase, Alexander Wolff and Johannes Zink  
14:40 - 15:00 Outside-Obstacle Representations with All Vertices on the Outer Face 20 Oksana Firman, Philipp Kindermann, Jonathan Klawitter, Boris Klemz, Felix Klesen and Alexander Wolff  
15:00 - 15:30 Break      
Session 8     Chair: Sabine Cornelsen  
15:30 - 15:50 Computing a Feedback Arc Set Using PageRank 20 Vasileios Geladaris, Panagiotis Lionakis and Ioannis Tollis  
15:50 - 16:10 st-Orientations with Few Transitive Edges 20 Carla Binucci, Walter Didimo and Maurizio Patrignani  
16:10 - 16:30 Testing Upward Planarity of Partial 2-Trees 20 Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati, Robert Ganian, Chrysanthi Raftopoulou and Kirill Simonov  
16:30 - 16:50 Visibility representations of toroidal and Klein-bottle graphs 20 Therese Biedl  
16:50 - 17:10 Voting best presentation and closing      


Keynote Speakers

Ulrik Brandes (ETH Zürich, Switzerland)

Title:

Positions in Social and Other Spaces

Abstract:

Social networks are a traditional source of inspiration for graph drawing methods, and their analysis continues to motivate a variety of layout constraints and objectives.

In recent years, my research has increasingly been focused on methodological questions related to social networks and other applied areas of network science. This has led to a framework, dubbed the positional approach, which facilitates adaptive and theory-informed empirical network data science. It turns out, however, that it is also another rich source of algorithmic and visualization problems. The present contribution is therefore forward-looking, using results from the past few years to point out possible directions for future research in three parts.

In the first part, I review some defining aspects of the positional approach to network science with an eye towards challenges for graph drawing and network visualization. These are centered largely on combinatorial problems involving preorders and graph classes.

A particularly strong link between influence processes on social networks and barycentric graph drawing is discussed in the second part. Using concepts from above, this extends naturally to calls for novel scaling methods and research on graph embeddings.

The final part is about collectice behavior in the context of team sports. More precisely, I will outline problems arising from our most recent efforts of performance analysis in association football (soccer) using proximity graphs.

Biography:

Ulrik Brandes is professor for social networks at ETH Zürich. His background is in computer science; he obtained a Diploma degree from RWTH Aachen and a doctoral degree from the University of Konstanz with a dissertation on graph drawing. After his habilitation in 2002 he became associate professor at the University of Passau in the same year, and professor for algorithmics at the University of Konstanz one year later. He is vice-president of the International Network for Social Network Analysis (INSNA), coordinating editor of Network Science, and on the editorial boards of Social Networks, Journal of Mathematical Sociology, Journal of Graph Algorithms and Applications, and Computer Science Review. From 2007-2014 he served on the Graph Drawing Steering Committee.
His main interests are in network analysis and visualization, with application to social networks in particular. He is a co-author of the visone software for network analysis and the GraphML data format. Following a DFG-funded Reinhart Koselleck-Project (2011-2017) on Social Network Algorithmics, he takes a shot at improving the methodological foundations of network science. As a principal investigator in the ERC Synergy Project NEXUS 1492 (2013-2019) he worked on reconstructing archaeological networks from fragmented and heterogeneous observations. Currently, he is devoting more time to network representations in sports analytics.

Kazuo Misue‬ (University of Tsukuba, Japan)

Title:

Graph Drawing for Thinking Support

Abstract:

In human intellectual activities, organizing the objects of thought is an important task. When the object of thought is large or complex, it is difficult for many people to organize it in their minds. In such cases, it is effective to take these objects out of our minds and observe them externally. When we externalize our thoughts in this way, the form of representation of the objects also influences the effectiveness and efficiency of our thinking process. When we organize fragments of information, we often establish a relationship between two fragments and group several fragments together. In the case of externalization, these relationships and groups are represented graphically, that is, the words and figures representing the fragments are connected by line segments or surrounded by closed lines. Some of the so-called "ideation techniques" systematize such diagramming methods. The "KJ method" is one such technique.

In the diagram used in the KJ method, if each fragment of information is represented by a node, links connecting two nodes and closed curves surrounding the nodes are used. Moreover, in the KJ method, we can organize objects of thought by transforming a compound diagram that comprises a node-link diagram and an Euler diagram. The original KJ method was designed to be performed entirely by hand using analog tools such as cards, pens, and cords, and it was not intended for the use with computers. This, however, is also a factor that discourages the active use of the KJ method, although its usefulness as an ideation technique has been recognized. For example, despite the effectiveness of repeated drawing of diagrams on the same topic, we often do so only once because repeating the process requires time and effort.

The transformation operation of a compound diagram can be viewed as the transformation operation of a compound graph; to obtain a visual representation of such a compound graph, automatic drawing techniques are required. If we can separate the transforming operations of a compound diagram from the thinking process and if the transforming operations can be supported by a computer, the hurdles associated with the use of such an ideation technique will be reduced, and the efficiency of the ideation process could increase. Eventually, this increased efficiency will lead to an improvement in the quality of the ideation process and its products.

This talk introduces the research and development that has been carried out with this motivation.

Biography:

Kazuo Misue is a professor at the Faculty of Engineering, Information and Systems, University of Tsukuba, Japan. He received a BSc and an MSc from Tokyo University of Science in 1984 and 1986. He received a Ph.D. in engineering from the University of Tokyo in 1997. He joined Fujitsu Limited in 1986. He worked at the International Institute for Advanced Study of Social Information Sciences, where he worked with Kozo Sugiyama and others on the research and development of graph drawing and idea support tools. In 2004, he moved to the University of Tsukuba. He has been involved in the development of visualization methods not only for graph drawing but also for various types of data. In 2021, he published "Introduction to Information Visualization (Japanese)," which organized the knowledge he had collected so far.

Accepted Papers

  • Andrew Suk and Ji Zeng. Unavoidable patterns in complete simple topological graphs

  • Steven Chaplick, Philipp Kindermann, Jonathan Klawitter, Ignaz Rutter and Alexander Wolff. Morphing Rectangular Duals

  • Therese Biedl. Visibility representations of toroidal and Klein-bottle graphs

  • Jacob Fox, Janos Pach and Andrew Suk. Quasiplanar graphs, string graphs, and the Erdős-Gallai problem

  • Sabine Cornelsen and Gregor Diatzko. Planar Confluent Orthogonal Drawings of 4-Modal Digraphs

  • Grzegorz Gutowski, Florian Mittelstädt, Ignaz Rutter, Joachim Spoerhase, Alexander Wolff and Johannes Zink. Coloring Mixed and Directional Interval Graphs

  • Rosna Paul, Oswin Aichholzer, Kristin Knorr, Birgit Vogtenhuber, Johannes Obenaus, Wolfgang Mulzer, Nicolas El Maalouly, Meghana M Reddy and Alexandra Weinberger. Compatible Spanning Trees in Simple Drawings of $K_n$

  • Soeren Nickel, Martin Nöllenburg, Manuel Sorge, Anaïs Villedieu, Hsiang-Yun Wu and Jules Wulms. Planarizing Graphs and their Drawings by Vertex Splitting

  • Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati, Robert Ganian, Chrysanthi Raftopoulou and Kirill Simonov. Testing Upward Planarity of Partial 2-Trees

  • Velitchko Filipov, Alessio Arleo, Markus Bögl and Silvia Miksch. On Time and Space: An Experimental Study on Graph Structural and Temporal Representations

  • Giuseppe Di Battista, Walter Didimo, Luca Grilli, Fabrizio Grosso, Giacomo Ortali, Maurizio Patrignani and Alessandra Tappini. Small Point-Sets Supporting Graph Stories

  • Carla Binucci, Emilio Di Giacomo, William J. Lenhart, Giuseppe Liotta, Fabrizio Montecchiani, Martin Nöllenburg and Antonios Symvonis. On the Complexity of the Storyplan Problem

  • Oksana Firman, Philipp Kindermann, Jonathan Klawitter, Boris Klemz, Felix Klesen and Alexander Wolff. Outside-Obstacle Representations with All Vertices on the Outer Face

  • Stefan Felsner, Sandro Roch and Manfred Scheucher. Arrangements of Pseudocircles: On Digons and Triangles

  • Sergey Pupyrev. Queue Layouts of Two-Dimensional Posets

  • Carlos Alegría, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Fabrizio Grosso and Maurizio Patrignani. Unit-length Rectangular Drawings of Graphs

  • Michael Bekos, Martin Gronemann, Fabrizio Montecchiani and Antonios Symvonis. Strictly-Convex Drawings of 3-Connected Planar Graphs

  • Kathryn Gray, Mingwei Li, Abu Reyan Ahmed and Stephen Kobourov. Visualizing Evolving Trees

  • Vasileios Geladaris, Panagiotis Lionakis and Ioannis Tollis. Computing a Feedback Arc Set Using PageRank

  • Kazuo Misue. Improved Scheduling of Morphing Edge Drawing

  • Jacob Miller, Vahan Huroyan and Stephen Kobourov. Spherical Graph Drawing by Multidimensional Scaling

  • William Lenhart and Giuseppe Liotta. Mutual Witness Gabriel Drawings of Complete Bipartite Graphs

  • Amyra Meidiana, Seok-Hee Hong and Peter Eades. Shape-Faithful Graph Drawings

  • Michael Bekos, Giordano Da Lozzo, Fabrizio Frati, Martin Gronemann, Tamara Mchedlidze and Chrysanthi Raftopoulou. Recognizing DAGs with Page-Number 2 is NP-complete

  • Carla Binucci, Walter Didimo and Maurizio Patrignani. st-Orientations with Few Transitive Edges

  • Michael Bekos, Stefan Felsner, Philipp Kindermann, Stephen Kobourov, Jan Kratochvíl and Ignaz Rutter. The Rique-Number of Graphs

  • Loann Giovannangeli, Frédéric Lalanne, Romain Giot and Romain Bourqui. FORBID: Fast Overlap Removal By Stochastic Gradient Descent for Graph Drawing

  • Alfredo Garcia, Javier Tejel, Birgit Vogtenhuber and Alexandra Weinberger. Empty Triangles in Generalized Twisted Drawings of K_n

  • Walter Didimo, Michael Kaufmann, Giuseppe Liotta and Giacomo Ortali. Rectilinear Planarity of Partial 2-Trees

  • Oswin Aichholzer, Alfredo Garcia, Irene Parada, Birgit Vogtenhuber and Alexandra Weinberger. Shooting Stars in Simple Drawings of K_{m,n}

  • Otfried Cheong, Maximilian Pfister and Lena Schlipf. The thickness of fan-planar graphs is at most three

  • Reyan Ahmed, Stephen Kobourov and Myroslav Kryven. An FPT Algorithm for Bipartite Vertex Splitting

Accepted Posters

Onsite Posters

  • Ryosuke Saga, Tomoki Yoshikawa and Tomoharu Nakashima. Edge Bundling by Density-based Pathfinding Approach

Online Posters

  • Mykyta Shvets, Ehsan Moradi and Debajyoti Mondal. Visualizing Node-Specific Hierarchies in Directed Networks

  • Simon van Wageningen and Tamara Mchedlidze. Can an ML Model plainly learn Planar Layouts?

  • Giuseppe Liotta, Maarten Loffler, Fabrizio Montecchiani, Alessandra Tappini and Soeren Terziadis. The Witness Unit Disk Representability Problem

  • David Trye, Mark Apperley and David Bainbridge. Aggregating Hypergraphs by Node Attributes

Updated: