Past Winner
2005 NSERC Doctoral Prize

Vida Dujmović

Software and Development

McGill University

In an age of supercomputers it might seem hard to believe that there remain some mathematical problems that are too difficult to crack computationally. But where brute processing strength has failed, Dr. Vida Dujmović has sought a mathematical compromise with Nature: if the whole answer is too much, at least give us part of it.

In doing so, the recent McGill University computer science Ph.D. recipient has created solutions to mathematical problems that have stymied scientists for years. Her insights could have applications from engineering to genetics, and have earned her a 2005 NSERC Doctoral Prize – one of Canada's premier graduate student awards.

Dr. Dujmović's attention is focused on mathematical graphs. These aren't statistical charts, but rather mathematical structures used to represent relationships between different objects. For example, the Internet can be visually represented as a graph. Each computer is a node on the graph and each connection is referred to as an edge.

The challenge with real world graphs is that they must be visually represented in ways that are easy to read or make.

"When a graph drawing is to be displayed on a page or a computer screen, or is to be used for integrated circuit design, it is important to keep the area of the drawing small to avoid wasting space. And more often than not, the idea of a nice graph drawing, regardless of its purpose, coincides with having no, or very few, edge crossings," says Dr. Dujmović, who's presently an NSERC Postdoctoral Fellow at Carleton University in Ottawa.

However many graph problems – dubbed "intractable problems" – are just too difficult to solve computationally without having a computer whirring away for days or months.

Rather than trying to crack this whole nut, Dr. Dujmović and her doctoral supervisor Dr. Sue Whitesides, developed efficient algorithms, or computational commands, that solve these problems by seeking the best possible answer when the ideal is not achievable. Called fixed parameter tractable algorithms, they are able to rapidly solve otherwise intractable graph problems by setting a fixed parameter, such as no more than 100 edge crossings, as a constant. Given a graph input, the algorithm automatically generates a two-dimensional drawing with a small number of edge crossings.

This doctoral research also turned new ground in the realm of 3-D graphs. Here, like organizing clothes in a stuffed suitcase, the challenge is to pack the graph into as small a volume as possible. Dr. Dujmović discovered types of graphs for which “crossing-free” 3-D drawings with a small volume always exist.

Presently Dr. Dujmović is still trying to discover ever faster and better graph algorithms.

"I don't know what practical difference my work may make," says Dr. Dujmović of her theoretical research. "What we are really concerned with is studying the fundamental gist of things. In general, which scientific advances may have such practical benefit cannot always be predicted. Sometimes it is the most seemingly impractical scientific advances that make a difference."