# Algorithmics for Beyond Planar Graphs

**NII Shonan Meeting: ** **@ Shonan Village Center****, November28-December 1, 2016**

## Organizers

- Seok-Hee Hong, The University of Sydney, Australia
- Takeshi Tokuyama, Tohoku University, Japan

## Overview

**Description of the meeting:**

**Summary:**

Many existing graph algorithms have a strong assumption that the input graph is planar, however, most graphs such as social networks or biological networks in real-world applications are non-planar.

This workshop aims to solve algorithmic problems for sparse non-planar graphs, with specific application of large and complex network visualisation. More specifically, we will develop innovative algorithms to handle sparse non-planar graphs such as k-planar graphs, k-skew graphs, and k-quasi-planar graphs:

k-planar graphs: a graph is k-planar if it has a drawing in which no edge crosses more than k edges.

k-skew graphs: a graph is k-skew if it has a drawing in which deletion of k edges makes the resulting graph planar.

k-quasi-planar graphs: a graph is k-quasi-planar if it has a drawing in which no k edges mutually cross each other.

The main goal of the workshop is to promote Graph Algorithm research in Asia-Pacific region, and form a research community to collaboratively solve complex problems arising in a variety of application domains such as social networks or systems biology. In particular, special emphasis on the “Beyond Planar Graphs” will be addressed.

**Aims:**

This workshop aims to bring world-renowned researchers on Graph Algorithm, Graph Drawing, Computational Geometry, and Graph Theory, and collaboratively develop innovative theory and algorithms for sparse non-planar topological graphs with specific applications of large and complex network visualization.

More specifically, we have the following aims:

Structural properties: We aim to characterise classes of sparse non-planar topological graphs. We aim to find important structural properties of such graphs.

Testing algorithm: We aim to design algorithms to test whether a given graph satisfies such topological constraints in polynomial time. We want to determine whether each of these problems is NP-hard. If not, we will design efficient (polynomial time) algorithms.

Drawing algorithm: We aim to design polynomial time algorithms to construct a straight-line drawing of an embedding that satisfies topological constraints.

**Objectives:**

We will identify research opportunities on Beyond Planar Graphs, focusing on the Asia-Pacific context.

We will form a broader research community with cross-disciplinary collaboration, between Computer Science (Graph Algorithm, Theoretical Computer Science, Combinatorial Optimisation) as well as Mathematics (Graph Theory, Combinatorics).

We will foster greater exchange between Graph Drawing community, Computational Geometry community and Graph Theory community, and to draw more researchers in the Asia-Pacific region to enter this rapidly growing area of research.

We will assist emerging researchers to find linkages to international researchers and competitive research grants and fundings.

**Significance and Innovation:**

Existing planar graph drawing algorithms have made little impact on visualisation of real-world complex networks. This workshop will be the first general and extensive investigation of the algorithmic questions arising from sparse non-planar topological graphs for real-world network visualisation.

We believe that this workshop will set a new research agenda in Graph Drawing and Geometric Graph Theory. More specifically, our innovations include:

New research agenda for Graph Drawing: This workshop will develop new algorithms that address the problems of sparse non-planar topological graphs. It will form a significant chapter in the grand tradition of interplay between geometry and combinatorial structures.

New Visualisation algorithms for real world networks: The innovation lies in designing novel algorithms for good visualisations of real world networks, which are sparse non-planar. The drawing algorithms will be used by industry and other disciplines (such as biology and sociology) to visualise real world networks.

**Expected Outcomes:**

Innovative techniques and solutions for Beyond Planar Graphs, which will be used by domain experts and end users in various application.

Joint publications at the top conferences and journals in Algorithms and Theory, jointly authored by researchers in Graph Algorithm, Graph Drawing, Computational Geometry, Combinatorial Optimisation, and Graph Theory.

Joint funding applications for long-term research collaboration for continuation of the research collaboration beyond 2016.

**Impact:**

Academic impact: research publications at top conferences and journals, with high citations.

Social impact: new algorithms for Beyond Planar Graphs will be in high-demand by researchers and practitioners in various applications and disciplines to solve complex problems in their domains.