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.

• 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]