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.

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.

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

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.

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

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