Graph Drawing Research

My significant contributions cover both theory and practice of Graph Drawing:

  • From the theoretical point of view, Graph Drawing involves a number of fundamental scientific challenges, spanning the mathematical theories of graph theory, geometry and topology, as well as computational theories such as NP-completeness and computational geometry.
  • From the practical point of view, my Graph Drawing research has enabled improvements in visualisation software that have been applied across a broad range of industries.

I have focused on designing new algorithms that create good geometric representations of graphs. I draw on a broad range of real-world applications in software engineering, sensor networks,biotechnology, health informatics, and security (money laundering and fraud detection). These industries need good visual representations of graphs to make it possible for humans to understand large data sets easily and quickly.



(1)  Symmetric Graph Drawing

I developed an optimal algorithm for drawing planar graphs with maximum symmetry. This solved a fundamental problem that had been open for more than 10 years, after Manning asked in 1990 whether planar graphs can be drawn symmetrically in polynomial time, or whether an NP-complete problem is involved. This advance established symmetric graph drawing as a fundamental research direction in algorithmics, underpinned by research from the mathematical fields of geometry, graph theory, group theory and knot theory.
I used connectivity approach (disconnected, one-connected, biconnected and triconnected) based on graph decomposition techniques (SPQR trees and BC trees). In particular, I used a group-theoretic approach to solve the problem by making close connections between symmetric graph drawing and graph automorphism. The optimal algorithm can compute maximally symmetric drawings of planar graphs in linear time, even though an exponential number of drawings are possible for planar graphs.
I received the 2006 Chris Wallace Award for Outstanding Research Contribution in Computer Science from CORE, for a "notable breakthrough or a contribution of particular significance" to the theory and practice of graph drawing.



(2)  2.5D Graph Visualisation Framework

I observed that, unlike 2D graph drawing, 3D graph drawing had little or no commercial impact, even though it has attracted significant theoretical interest. There were two major problems for 3D visualisation: occlusion and interaction. With the specific aim of producing science that would have a commercial impact in 3D graph visualisation, I developed a new 2.5D framework for graph visualisation. The human experiments on 2.5D representation by Ware supported usefulness of such metaphor. My contribution was critical in developing an algorithm-based framework that enabled 2.5D representations to be applied to the depiction of real-world networks. The innovation minimises both the occlusion and interaction problems in 3D graph drawing.
With VALACON team members, I used this framework to produce visualisations of social networks and biological networks; the results won four first prizes at the IEEE InfoVis contest in 2004, the international Graph Drawing competitions in 2005 and 2006.



(3)  New theories in Graph Drawing

I have initiated new fundamental theories in graph drawing. These theories enabled me to pose new research problems on the basis of real-world problems for which there were no practical solutions - for example, they gave sensor network visualisation with a given floorplanning.
My algorithmic solutions generalised three seminal results from mathematics: Steinitz's theorem (1922), Tutte's barycentre theorem (1960), and Fary's theorem (1948). These theorems have limitations for real-world applications, due to their restrictive assumptions on the input graph connectivity. I provided practical solutions and efficient constructive algorithms for real-world problems and real-world biconnected graphs. This has initiated a new research area in graph drawing, provided efficient and effective solutions to sensor network visualisation, and made advances in the underlying mathematics.



(4)  Other Graph Drawing Research



  Visualisation of Massive and Complex Network

Technological advances are producing exponentially increasing amounts of data. Consequently, massive complex networks have evolved in many domains with millions, even billions of nodes, all with complex relationships. Domains include finance, science and engineering such as:

  • social networks: Facebook, Twitter, Linked-In, Wikepedia, as well as telephone call graphs (used to trace terrorists) and money movement networks (for detecting money laundering).
  • biological networks: protein interaction networks, biochemical pathways, and gene regulatory networks.

    • Visualisation is a powerful analytical tool for massive complex networks. Good visualisation can amplify human cognition, reveal hidden structure of a network, thus leading to new insights, findings and predictions. However, creating good visualisations of these networks is extremely challenging.
    Many real world networks can be modelled mathematically as "graphs". Graph Drawing is the science and art of creating good geometric representations of a graph. The resulting visualisation needs to convey information faithfully. Researchers have established that "good" visualisations have some geometric properties, called "aesthetic criteria" including: few edge crossings, good area resolution (small area in 2D and small volume in 3D), low curve complexity (few bends per edges), and a high degree of symmetry. Algorithms for constructing graph drawings with such properties have been the subject of a great deal of research. Creating such algorithms requires efficient solutions for difficult combinatorial and geometric optimisation problems.




      Scalable Visual Analytics for Dynamic Uncertain Networks

    My latest ARC DP0988838 project addressed the three practical challenges for graph visualisation: uncertainty, dynamics and interaction. The aim was to design a new visual analytics framework for uncertain dynamic networks.

    Our initial results included an integration of topology, geometry and importance to enable new knowledge discovery for complex protein-protein interaction networks. This work has been conducted in collaboration with a biology research group in Bielefeld University in Germany. The visualisations that we designed have generated hypotheses for the biology group; they have been conducting wetlab experiments to confirm their new hypothesis.



      NICTA VALACON (Visualisation and Analysis of Large and Complex Networks) Project



      Graph Drawing and Network Visualisation Tools