November 6 – 11 , 2016, Dagstuhl Seminar 16452
Beyond-Planar Graphs: Algorithmics and Combinatorics
1 / 3 >
For support, please contact
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.
Creative Commons BY 3.0 Unported license
Seokhee Hong, Michael Kaufmann, Stephen G. Kobourov, and János Pách
- Computer Graphics / Computer Vision
- Data Structures / Algorithms / Complexity
- Graph Drawing
- Graph Theory
- Combinatorial Geometry