MATHEMATICIAN RECEIVES PRESTIGIOUS PRIZE FOR GRAPH THEORY
By Pam Frost Gorder
As Neil Robertson explains his work using pen and paper, his drawings might look like a game of connect-the-dots gone horribly awry. But to this professor of mathematics at Ohio State University, the spoked wheels and branching tree shapes he draws actually represent phone lines, power lines, or computer chips on a circuit board.
Robertson’s vision has helped him and a colleague solve a longstanding problem in his field of graph theory, and recently earned them the prestigious George Polya Prize from the Society for Industrial and Applied Mathematics (SIAM).
In the award citation, the society praised Robertson and Paul Seymour -- formerly a professor at Ohio State and now at Princeton University -- for their proof of a mathematical hypothesis known as the Wagner Conjecture. SIAM called the proof a “true tour-de-force” with “deep and far-reaching consequences.”
Robertson and Seymour received their prize at the SIAM annual meeting in July, where they were awarded $10,000 each.
In general, graph theory deals with systems of points, called nodes, connected by lines. The Wagner Conjecture concerns how nodes are interrelated.
Understanding how large systems of nodes fit together is very complicated mathematically, but it’s critical when the nodes are telephone poles, and the lines are phone lines. Robertson and Seymour’s proof of the conjecture led to the development of computer algorithms that efficiently re-route calls around a downed line. Their work is just as applicable to cell phone routing, the placement of power lines, and even the microscopic wiring in computer chips.
“Neil's work with Paul Seymour on the Wagner Conjecture is the culmination of four years of intense work on the structure of infinite families of graphs,” Said Peter March, professor and chair of mathematics at Ohio State. “Their deep understanding of that structure allowed them to verify the conjecture and make a number of concrete applications to path-routing problems in communication networks.”
Robertson began thinking about the Wagner Conjecture before he joined the Ohio State faculty in 1969.
“I’d heard about it in graduate school, and thought it was a great problem to solve, but nobody knew where to start,” Robertson remembered.
Seymour came to Ohio State in 1980; The two began working on the problem in 1981, solved it by 1985, and have since spelled out their proof in a series of 20 research papers, the latest of which was just accepted for publication in the Journal of Combinatorial Theory B.
Their decades-long collaboration has spawned not only their proof of the Wagner Conjecture, but a whole family of theorems that are required reading for any student of graph theory.
Robertson has received numerous other awards, including the Fulkerson Prize from the Mathematical Programming Society in 1994, Ohio State’s Distinguished Scholar Award in 1997, and the Alumni Achievement Medal from his graduate institution, the University of Waterloo, in 2002.