Basser Seminar Series

Theory and Practice of Graph Drawing

Dr Seokhee Hong
University of Sydney and NICTA
and winner of the 2006 Computing Research And Education Association (CORE) Chris Wallace Award for outstanding research contribution 2006

Wednesday 7 June 2006, 4-5pm and followed by refreshments
Carslaw Lecture Theatre 373 (please note different location)

Please rsvp to Wei-ying Ho: weiying@it.usyd.edu.au or 9351 4917 by Thursday 1 June 2006

Abstract

Part 1. Theory of Graph Drawing

Graph Drawing is the construction of geometric representations of graphs in two or three dimensions. Symmetry is one of the most important aesthetic criteria in Graph Drawing. It clearly reveals the structure of an abstract graph. The problem of determining whether a graph can be drawn symmetrically is NP-complete. However, the problem can be solved in polynomial time for several restricted classes of graphs such as trees, outerplanar graphs and planar graphs. The first part of this talk briefly covers recent results in Symmetric Graph Drawing including symmetry models, heuristics and exact algorithms for general graphs, and optimal algorithms for planar graphs.

Part 2. Practice of Graph Drawing

Recent technological advances have led to many large and complex network models in many domains, including social networks, biological networks, webgraphs and software engineering. Visualization can be an effective analysis tool for such networks. Good visualisation reveals the hidden structure of the networks and amplifies human understanding, thus leading to new insights, new findings and possible prediction of the future. However, visualisation of such large and complex networks is very challenging both in scalability and complexity. The second part of this talk briefly addresses these challenging issues for visualisation of large and complex networks and briefly introduce new methods for good visualisation of large and complex social networks and biological networks.

Speaker's biography

Dr. Seokhee Hong is a senior lecturer at the University of Sydney and a Project leader of NICTA (National ICT Australia). Dr. Hong received BSc, MSc and PhD from Ewha University in Korea. She won the KOSEF (Korea Science and Engineering Foundation) Postdoctoral Fellowship which she undertook at the University of Newcastle in 1999. In 2000, she accepted a Postdoctoral Research Fellow position with the Basser Department of Computer Science at the University of Sydney. She joined as a lecturer at the School of Information Technologies, University of Sydney in 2001. Dr. Hong obtained a number of research grants including ARC Linkage grant and ARC Discovery grant. Currently, she is working as a Project leader of NICTA VALACON (Visualisation and Analysis of Large and Complex Networks) project. She is the winner of CORE Chris Wallace Award 2006 for her outstanding research contribution in the field of computer science for her research in "Theory and Practice of Graph Drawing".