http://www.dagstuhl.de/16452

November 6 – 11 , 2016, Dagstuhl Seminar 16452

Beyond-Planar Graphs: Algorithmics and Combinatorics

Organizers

Seokhee Hong (The University of Sydney, AU)
Michael Kaufmann (Universität Tübingen, DE)
Stephen G. Kobourov (University of Arizona – Tucson, US)
János Pách (EPFL – Lausanne, CH)


1 / 3 >

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 6, Issue 11 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents

Summary

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.

License
  Creative Commons BY 3.0 Unported license
  Seokhee Hong, Michael Kaufmann, Stephen G. Kobourov, and János Pách

Classification

  • Computer Graphics / Computer Vision
  • Data Structures / Algorithms / Complexity

Keywords

  • Graph Drawing
  • Graph Theory
  • Combinatorial Geometry

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.