24. Februar – 01. März 2019, Dagstuhl-Seminar 19092

Beyond-Planar Graphs: Combinatorics, Models and Algorithms


Seok-Hee Hong (The University of Sydney, AU)
Michael Kaufmann (Universität Tübingen, DE)
János Pach (EPFL – Lausanne, CH)
Csaba D. Tóth (California State University – Northridge, US)

Auskunft zu diesem Dagstuhl-Seminar erteilen

Dagstuhl Service Team zu administrativen Fragen

Andreas Dolzmann zu wissenschaftlichen Fragen


Gemeinsame Dokumente


Most big data sets are relational, containing a set of objects and relations between the objects. This is commonly modeled by graphs, 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 has been extensively studied. Many structural properties of planar graphs are known, for example, in terms of excluded minors, low density, and small separators. These properties lead to efficient algorithms; 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 nonplanar. In particular, the class of scale-free networks, which can be used to model web-graphs, social networks and many kinds of biological networks, are sparse nonplanar graphs, with globally sparse and locally dense structure. To analyze and visualize such real world networks, we need to solve fundamental mathematical and algorithmic research questions on sparse nonplanar graphs. Sparsity, in most cases, is explained by properties that generalize planar graphs: in terms of topological obstructions or forbidden intersection patterns among the edges.

A recent research topic in topological graph theory generalizes the notion of planarity to beyond-planar graphs, (i.e., nonplanar graphs that admit a planar representation that follows certain topological constraints such as specific types of crossings, or avoiding some forbidden crossing patterns), including:

  • k-planar graphs: graphs that can be drawn with at most k crossings per edge;
  • k-quasi-planar graphs: graphs which can be drawn without k mutually crossing edges;
  • k-gap-planar graphs: graphs that admit a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most k of its crossings;
  • RAC (Right Angle Crossing) graphs: graphs that have straight-line drawings in which any two crossing edges meet in a right angle;
  • bar k-visibility graphs: graphs whose vertices are represented as horizontal segments (bars) and edges are represented as vertical lines connecting bars, intersecting at most k bars;
  • fan-crossing-free graphs: graphs which can be drawn without fan-crossings; and
  • fan-planar graphs: graphs which can be drawn such that every edge is crossed only by pairwise adjacent edges (fans).

This Dagstuhl Seminar will investigate beyond-planar graphs. It will explore, in particular, their combinatorial structure (i.e., thickness, density, coloring), geometric and topological obstructions (i.e., crossing numbers, stretchability, polyline drawing, geometric representation), recognition algorithms and applications (optimization, real-world network visualization). Behind the fundamental scientific challenges of this seminar lies the pragmatic need for better network visualization algorithms.<7p>

  Creative Commons BY 3.0 DE
  Seok-Hee Hong, Michael Kaufmann, János Pach, and Csaba D. Tóth

Related Dagstuhl-Seminar


  • Data Structures / Algorithms / Complexity
  • Networks


  • Graph drawing
  • Geometric algorithms
  • Combinatorial geometry
  • Graph algorithms
  • Graph theory
  • Network visualization


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.