Dagstuhl Seminar 24062
Beyond-Planar Graphs: Models, Structures and Geometric Representations
( Feb 04 – Feb 09, 2024 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/24062
Organizers
- Vida Dujmovic (University of Ottawa, CA)
- Seok-Hee Hong (The University of Sydney, AU)
- Michael Kaufmann (Universität Tübingen, DE)
- János Pach (Alfréd Rényi Institute - Budapest, HU & EPFL - Lausanne, CH)
Contact
- Andreas Dolzmann (for scientific matters)
- Christopher Michels (for administrative matters)
Schedule
Many big data sets in various application domains have complex relationships, which can be modeled as graphs, consisting of entities and relationships between them. Consequently, graphs are extensively studied in both mathematics and computer science. In particular, planar graphs, which can be drawn without edge crossings in the plane, form a distinguished role in graph theory and graph algorithms. Many structural properties of planar graphs are investigated in terms of excluded minors, low density, and small separators, leading to efficient planar graph algorithms. Consequently, fundamental algorithms for planar graphs have been discovered.
However, most real-world graphs, such as social networks and biological networks, are nonplanar. For example, the scale-free networks, which are used to model web graphs, social networks, and biological networks, are globally sparse nonplanar graphs with locally dense clusters and low diameters. To understand such real-world networks, we must solve fundamental mathematical and algorithmic research questions on beyond-planar graphs, which generalize the notion of planar graphs regarding topological constraints or forbidden edge crossing patterns.
This Dagstuhl Seminar investigated beyond-planar graphs, in particular, their combinatorial and topological structures (i.e., density, thickness, crossing pattern, chromatic number, queue number, and stack number), computational complexity and algorithmics for recognition, geometric representations (i.e., straight-line drawing, polyline drawing, intersection graphs), and their applications to real-world network visualization.
Compared to the previous two editions of the seminar, we focus more on aspects of combinatorics and geometry. Therefore, we included one new organizer and more participants from the corresponding fields. Thirty-two participants accepted the invitation to participate and arrived on Sunday afternoon.
On Monday morning, the program started with an introduction of all participants, followed by four invited talks to provide fundamental background knowledge on related research fields. We organized an open problems session on Monday afternoon and formed new working groups for research collaboration.
Many new problems related to combinatorics and geometry of beyond-planar graphs have been proposed. Specific open problems include questions regarding the combinatorial structures and topology (e.g., k+-real face graphs, beyond upward planar graphs, sparse universal geometric graphs, local-crossing-critical graphs), the geometric representations (e.g., constrained outer string graphs, rerouting curves on the surface), and applications.
Two progress report sessions were organized on Tuesday and Thursday afternoons to report progress and plans for future publications and follow-up meetings among researchers. From the participants’ feedback, the seminar has initiated new research collaboration and led to new research ideas and directions.
Taking this opportunity, we thank Schloss Dagstuhl for providing an environment for fruitful research collaboration.
Creative Commons BY 4.0
Vida Dujmovic, Seok-Hee Hong, Michael Kaufmann, and János Pach
Many big data sets in various application domains have complex relationships, which can be modelled as graphs, consisting of entities and relationships between them. Consequently, graphs are extensively studied in both Mathematics and Computer science.
In particular, planar graphs, which can be drawn without edge crossings in the plane, form a distinguished role in Graph Theory and Graph Algorithms. Many structural properties of planar graphs are investigated, in terms of excluded minors, low density, and small separators, which lead to efficient algorithms for planar graphs. Consequently, fundamental algorithms for planar graphs have been discovered.
However, most real-world graphs, such as social networks and biological networks, are nonplanar. For example, the scale-free networks, which are used to model web graphs, social networks and biological networks, are globally sparse nonplanar graphs, with locally dense clusters and low diameters. To understand such real-world networks, we need to solve fundamental mathematical and algorithmic research questions on beyond-planar graphs, which generalize the notion of planar graphs, in terms of topological constraints or forbidden edge crossing patterns.
This Dagstuhl Seminar will investigate beyond-planar graphs, in particular, their combinatorial and topological structures (i.e., density, thickness, crossing pattern, chromatic number, queue number, and stack number), computational complexity and algorithmics for recognition, geometric representations (i.e., straight-line drawing, polyline drawing, intersection graphs), and their applications to real-world network visualization. Behind the fundamental scientific challenges and significant advances of this seminar lies the pragmatic need for effective visualization algorithms of real-world big complex networks.
Vida Dujmovic, Seok-Hee Hong, Michael Kaufmann, and János Pach
- Patrizio Angelini (John Cabot University - Rome, IT) [dblp]
- Michael A. Bekos (University of Ioannina, GR) [dblp]
- Therese Biedl (University of Waterloo, CA) [dblp]
- Markus Chimani (Universität Osnabrück, DE) [dblp]
- Sabine Cornelsen (Universität Konstanz, DE) [dblp]
- Giordano Da Lozzo (University of Rome III, IT) [dblp]
- Giuseppe Di Battista (University of Rome III, IT) [dblp]
- Emilio Di Giacomo (University of Perugia, IT) [dblp]
- Walter Didimo (University of Perugia, IT) [dblp]
- Vida Dujmovic (University of Ottawa, CA) [dblp]
- Stefan Felsner (TU Berlin, DE) [dblp]
- Henry Förster (Universität Tübingen, DE) [dblp]
- Fabrizio Frati (University of Rome III, IT) [dblp]
- Michael Hoffmann (ETH Zürich, CH) [dblp]
- Seok-Hee Hong (The University of Sydney, AU) [dblp]
- Michael Kaufmann (Universität Tübingen, DE) [dblp]
- Stephen Kobourov (University of Arizona - Tucson, US) [dblp]
- Jan Kratochvil (Charles University - Prague, CZ) [dblp]
- Giuseppe Liotta (University of Perugia, IT) [dblp]
- Anna Lubiw (University of Waterloo, CA) [dblp]
- Fabrizio Montecchiani (University of Perugia, IT) [dblp]
- Pat Morin (Carleton University - Ottawa, CA) [dblp]
- Yoshio Okamoto (The University of Electro-Communications - Tokyo, JP) [dblp]
- János Pach (Alfréd Rényi Institute - Budapest, HU & EPFL - Lausanne, CH) [dblp]
- Maurizio Patrignani (University of Rome III, IT) [dblp]
- Sergey Pupyrev (Facebook - Menlo Park, US) [dblp]
- Ignaz Rutter (Universität Passau, DE) [dblp]
- Csaba Tóth (California State University - Northridge, US) [dblp]
- Géza Tóth (Alfréd Rényi Institute of Mathematics - Budapest, HU) [dblp]
- Torsten Ueckerdt (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Pavel Valtr (Charles University - Prague, CZ) [dblp]
- Alexander Wolff (Universität Würzburg, DE) [dblp]
Related Seminars
Classification
- Computational Geometry
- Data Structures and Algorithms
- Discrete Mathematics
Keywords
- Graph drawing
- Graph algorithm
- Graph theory
- Combinatorial geometry
- Network visualization
