Dagstuhl Seminar 16452
Beyond-Planar Graphs: Algorithmics and Combinatorics
( Nov 06 – Nov 11, 2016 )
Permalink
Organizers
- Seok-Hee Hong (The University of Sydney, AU)
- Michael Kaufmann (Universität Tübingen, DE)
- Stephen Kobourov (University of Arizona - Tucson, US)
- János Pach (EPFL - Lausanne, CH)
Contact
- Andreas Dolzmann (for scientific matters)
- Simone Schilke (for administrative matters)
Impacts
- On the Relationship between k-Planar and k-Quasi Planar Graphs : article in EuroCG 2017, Malmö, Sweden, April 5 : 7, 2017 : pp. 152-155 - Malmö : University, 2017 - (European Workshop on Computational Geometry 2017 ; article).
- On the Relationship Between k-Planar and k-Quasi-Planar Graphs : article in LNCS 10520 : WG 2017 - Angelini, Patrizio; Bekos, Michael A.; Brandenburg, Franz-Josef; Lozzo, Giordano Da; Battista, Giuseppe Di; Rutter, Ignaz; Montecchiani, Fabrizio ; Liotta, Giuseppe; Didimo, Walter - Berlin : Springer, 2017. - pp. 59-74 - (Lecture notes in computer science ; 10520 : article).
- Orthogonal and Smooth Orthogonal Layouts of 1-Planar Graphs with Low Edge Complexity - Argyriou, Evmorfia; Cornelsen, Sabine; Förster, Henry; Kaufmann, Michael; Nöllenburg, Martin; Wolff, Alexander; Raftopoulou, Chrysanthi N.; Okamoto, Yoshio - Cornell University : arXiv.org, 2018. - 25 pp..
- The number of crossings in multigraphs with no empty lens - Kaufmann, Michael; Pach, Janos; Toth, Geza; Ueckerdt, Torsten - Cornell University : arXiv.org, 2018. - 13 pp..
Regardless of the hype surrounding big data, the reality is that there is a great deal more data now then at any time in the past. Big-data challenges include efficiently organizing, processing, and storing the data, but arguably even more fundamental are the challenges of analyzing the structure and properties of the data, visualizing the data, and searching for patterns and trends.
Most data sets are relational, containing a set of objects and relations between the objects. This is commonly modeled by graphs and networks, with the objects as the vertices and the relations as the edges. A great deal is known about the structure and properties of special types of graphs, in particular planar graphs. The class of planar graphs is fundamental for both Graph Theory and Graph Algorithms, and extensively studied. Many structural properties of planar graphs are known; for example, a planar graph is sparse in that it can have at most 3n-6 edges, where n is the number of nodes in the graph. These properties lead to efficient algorithms for planar graphs, even where the more general problem is NP-hard. Consequently a number of fundamental algorithms for planar graphs have been discovered.
However, most real world graphs, such as social networks and biological networks, are non-planar. In particular, the class of scale-free networks, which can be used to model web-graphs, social networks and many kinds of biological networks, consists of sparse non-planar graphs. To analyze and visualize such real world networks, we need to solve fundamental mathematical and algorithmic research questions on sparse non-planar graphs, which we call beyond-planar graphs.
A recent research topic in topological graph theory generalizes the notion of planarity to beyond-planar graphs, i.e., non-planar graphs with topological constraints such as specific types of crossings, or with some forbidden crossing patterns. Examples of beyond-planar graphs include:
- k-planar graphs: graphs which can be embedded with at most k crossings per edge
- k-quasi-planar graphs: graphs which can be embedded without k mutually crossing edges
- bar k-visibility graphs graphs: graphs whose vertices are represented as horizontal segments (bars) and edges are represented as vertical lines connecting bars, intersecting at most k other bar
- fan-crossing-free graphs: graphs which can be embedded without fan-crossings
- fan-planar graphs: graphs which can be embedded with crossings sharing the common vertices
- RAC (Right Angle Crossing) graphs: a graph which has a straight-line drawing with right angle crossings
We aim to bring together world-renowned researchers in graph algorithms, computational geometry and graph theory, and collaboratively develop a research agenda for the study of beyond-planar graphs. We will also gather an annotated bibliography of this new field of study. Finally, we will work on specific open problems about the structure, topology, and geometry of beyond-planar graphs and consider their applications to network visualization.
Behind the fundamental scientific challenges of this Dagstuhl Seminar lies the pragmatic need for better network visualization algorithms. Leveraging the significant interplay between geometry and combinatorial structure, this seminar will allow us to put together a theoretically grounded research agenda for graph drawing and network visualization.
The seminar format of our seminar will accommodate introductory presentations, open-problem sessions, and problem-solving sessions. On the first day, selected representatives of the different communities will make introductory presentations. Discussion of the main open problems, the research agenda, and formation of working groups for the problems will also take place by the end of the first day. The remaining days will be dedicated to working-group meetings and progress reports. The initial drafts of the annotated bibliography and research directions documents will be finalized on the last day of the seminar.
Relational data sets, containing a set of objects and relations between them, are commonly modeled by graphs/networks, with the objects as the vertices and the relations as the edges. A great deal is known about the structure and properties of special types of graphs, in particular planar graphs. The class of planar graphs is fundamental for both Graph Theory and Graph Algorithms, and extensively studied. Many structural properties of planar graphs are known and these properties can be used in the development of efficient algorithms for planar graphs, even where the more general problem is NP-hard.
Most real world graphs, however, are non-planar. In particular, many scale-free networks, which can be used to model web-graphs, social networks and biological networks, consists of sparse non-planar graphs. To analyze and visualize such real-world networks, we need to solve fundamental mathematical and algorithmic research questions on sparse non-planar graphs, which we call beyond-planar graphs. The notion of beyond-planar graphs has been established as non-planar graphs with topological constraints such as specific types of crossings or with some forbidden crossing patterns, although it has not been formally defined. Examples of beyond-planar graphs include:
- k-planar graphs: graphs which can be embedded with at most k crossings per edge.
- k-quasi-planar graphs: graphs which can be embedded without k mutually crossing edges.
- bar k-visibility graphs: graphs whose vertices are represented as horizontal segments (bars) and edges as vertical lines connecting bars, intersecting at most k other bars.
- fan-crossing-free graphs: graphs which can be embedded without fan-crossings.
- fan-planar graphs: graphs which can be embedded with crossings sharing the common vertices.
- RAC (Right Angle Crossing) graphs: a graph which has a straight-line drawing with right angle crossings.
The aim of the seminar was to bring together world-renowned researchers in graph algorithms, computational geometry and graph theory, and collaboratively develop a research agenda for the study of beyond-planar graphs. The plan was to work on specific open problems about the structure, topology, and geometry of beyond-planar graphs. One of the outcomes of the workshop might be an annotated bibliography of this new field of study.
On Sunday afternoon, 29 participants met at Dagstuhl for an informal get-together. Fortunately, there were no cancelations and everybody who registered was able to attend. On Monday morning, the workshop officially kicked off. After a round of introductions, where we discovered that eight participants were first-time Dagstuhl attendees, we enjoyed three overview talks about beyond-planar graphs from three different points of view. First, Géza Tóth from the Rényi Institute in Budapest talked about the combinatorics of beyond-planar graphs in connection to graph theory. Next, Giuseppe Liotta from the University of Perugia gave an overview about the connections between graph drawing and beyond-planar graphs and presented a taxonomy of related topics and questions. Finally, Alexander Wolff from the University of Würzburg discussed beyond-planar graphs in the context of geometry and geometric graph representations.
On Monday afternoon, we had lively open problem sessions, where we collected 20 problems covering the most relevant topics. The participants split into four groups based on common interest in subsets of the open problems. The last three days of the seminar were dedicated to working group efforts. Most of the groups kept their focus on the original problems as stated in the open problem session, while one group modified and expanded the problems; see Section 4. We had two progress reports sessions, including one on Friday morning, where group leaders were officially designated and plans for follow-up work were made. Work from one of the groups has been submitted to an international conference, and we expect further research publications to result directly from the seminar.
Arguably the best, and most-appreciated, feature of the seminar was the opportunity to engage in discussion and interactions with experts in various fields with shared passion about graphs, geometry and combinatorics. We received very positive feedback from the participants (e.g., scientific quality: 10.5/11, inspired new ideas: 23/25, inspired joint projects: 21/25) and it is our impression that the participants enjoyed the unique scientific atmosphere at the seminar and benefited from the scientific program. In summary, we regard the seminar as a success, and we are grateful for having had the opportunity to organize it and take this opportunity to thank the scientific, administrative, and technical staff at Schloss Dagstuhl.
![Copyright](https://www.dagstuhl.de/_Resources/Static/Packages/Dagstuhl.Site/Frontend/images/licenses/copy.png?bust=22575bbf)
- Muhammad Jawaherul Alam (University of California - Irvine, US) [dblp]
- Patrizio Angelini (Universität Tübingen, DE) [dblp]
- Evmorfia Argyriou (yWorks GmbH – Tübingen, DE) [dblp]
- Michael A. Bekos (Universität Tübingen, DE) [dblp]
- Franz J. Brandenburg (Universität Passau, DE) [dblp]
- Sabine Cornelsen (Universität Konstanz, DE) [dblp]
- Giordano Da Lozzo (University of California - Irvine, US) [dblp]
- Giuseppe Di Battista (Roma Tre University, IT) [dblp]
- Walter Didimo (University of Perugia, IT) [dblp]
- Stefan Felsner (TU Berlin, DE) [dblp]
- Kathrin Hanauer (Universität Passau, DE) [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]
- Giuseppe Liotta (University of Perugia, IT) [dblp]
- Fabrizio Montecchiani (University of Perugia, IT) [dblp]
- Quan Nguyen (The University of Sydney, AU) [dblp]
- Martin Nöllenburg (TU Wien, AT) [dblp]
- Yoshio Okamoto (The University of Electro-Communications - Tokyo, JP) [dblp]
- János Pach (EPFL - Lausanne, CH) [dblp]
- Sergey Pupyrev (Facebook - Menlo Park, US) [dblp]
- Chrysanthi Raftopoulou (National Technical University of Athens, GR) [dblp]
- Md. Saidur Rahman (Bangladesh University of Eng.& Technology, BD) [dblp]
- Vincenzo Roselli (Roma Tre University, IT) [dblp]
- Ignaz Rutter (TU Eindhoven, NL) [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
- computer graphics / computer vision
- data structures / algorithms / complexity
Keywords
- Graph Drawing
- Graph Theory
- Combinatorial Geometry