Basser Seminar Series

Algorithmic TurĂ¡n-type Problems and Graph Drawing

Speaker: Professor Peter Eades
School of Information Technologies, The University of Sydney

Time: Friday 26 March 2009, 4:00-5:00pm
Refreshments will be available from 3:30pm

Location: The University of Sydney, School of IT Building, Lecture Theatre (Room 123), Level 1

Add seminar to my diary

Abstract

A Turán-type problem asks for the maximum number of edges in a graph with some given forbidden configuration. Such problems have been investigated by mathematicians for centuries, but became popular with the Turán's 1941 paper on extremal graph theory.

Graph drawing makes pictures of relational data sets, such as social networks, as node-link diagrams. These pictures can greatly help human understanding, but the diagram has to be good. A tangled rat's nest of a diagram can be confusing rather than helpful. In the past 20 years, graph drawing researchers have produced algorithms that are used in many visualization systems.

Empirical work by Purchase, Huang, Ware and others suggest that the "tangled-ness" of a diagram can be measured by the absence of forbidden configurations in the Turán sense.

In this talk we discuss algorithmic aspects of Turán-type problems that relate to Graph Drawing.

Speaker's biography

Peter Eades obtained his PhD from the Australian National University in 1978, and has been a professor at the University of Sydney since 2000. He is one of several founders of "Graph Drawing", the art and science of presenting relational information in graphical form to humans, with a view to maximizing its comprehensibility.