In the world of mathematics and computer science, graphs are used to model complex systems that have applications in a wide variety of disciplines.
A graph is composed of a set of nodes (also known as vertices) where pairs of nodes can be connected by edges. The nodes in a graph represent individual entities, while the edges represent the relationships or connections between them.
Graphs can be used to represent a wide range of real-world scenarios, including road networks, computer and communication networks, social networks, molecule diagrams and networks underlying financial markets. By using graphs to model these scenarios, researchers can gain insight into various phenomena, such as the spread of (mis)information, the dynamics of online communities, and the migration of people.
Despite their simple appearance, graphs possess a rich and complex structure that has long intrigued mathematicians and researchers. Some classes of graphs are well understood, but others are much more complicated and are less, or even poorly, understood. Planar graphs are one such complex class.
Vida Dujmović, professor at uOttawa’s Faculty of Engineering, was able to solve some longstanding problems by discovering a groundbreaking theorem that answers the question “what is the global structure of planar graphs?” Such persistent problems often suggest that we lack understanding of something fundamental within the theory. In her pursuit of a better understanding of planar graphs, Vida, along with her close-knit group of international colleagues Gwenaël Joret (Belgium), Piotr Micek (Poland), Pat Morin (Canada), Torsten Ueckerdt (Germany), David R. Wood (Australia), developed the Product Structure Theorem for Planar Graphs.
The theorem proves that planar graphs can be expressed as a product of two well-understood and simple graphs: a path and a graph of treewidth 8.
This theorem allowed them to solve several long-standing problems, including a conjecture on adjacency labelling from 1988, a conjecture on queue layouts from 1992, and a conjecture on non-repetitive colouring from 2002.
“I have been inspired by the problem on queue layouts for more than 15 years. I would repeatedly come back to the problem with new toolkits, attacking it from different angles, but the ultimate conjecture kept on resisting despite progress made over the years,” says Vida.
Finally, it was the discovery of the product structure that led to solving the problem.
“As it sometimes happens in science and engineering, the tools discovered while trying to solve a problem turned out to be more important than the problem itself,” says Vida.
The product structure theorem appears to be one of those tools, given the sheer number of important problems it can resolve, not just by Vida and her colleagues, but also by the research community at large.
The Faculty of Engineering congratulates Vida Dujmović and her team for their remarkable contributions to graph theory. Individuals and organizations interested in collaborating with them may contact Vida Dujmović directly.