NO.089 Algorithmics for Beyond Planar Graphs

Shonan Village Center

November 28 - December 1, 2016 (Check-in: November 27, 2016 )


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


Description of the meeting:


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.

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.


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