# NO.089 Algorithmics for Beyond Planar Graphs

November 28 - December 1, 2016 (Check-in: November 27, 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.