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.
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
(4) Beyond Planarity Project
(5) 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.
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.
Graph Drawing and Network Visualisation Tools
Unlike 2D graph drawing, 3D graph drawing had little or no commercial impact, even though it has attracted
significant theoretical interest, due to two major problems in 3D visualisation: "occlusion" and "interaction". With
the specific aim of creating science that has a commercial impact in 3D graph visualisation, I have developed a
new framework for 2.5D graph visualisation. My innovation minimises both the occlusion and interaction
problems in 3D graph drawing. GEOMI-2 is open source software, which implements my 2.5D graph drawing
framework, released in 2011 November (http://geomi2.sourceforge.net/).