Program

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 [Best Paper Award (T1)]

• Steven Chaplick, Philipp Kindermann, Jonathan Klawitter, Ignaz Rutter and Alexander Wolff. Morphing Rectangular Duals [Best Presentation Award]

• 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 [Best Paper Award (T2)]

• 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 [Best Poster Award]

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 [Best Poster Award]

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