### 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.
#
Contact: Neil Robertson, (614) 292-0602; Robertson.7@osu.edu
Written by Pam Frost Gorder, (614) 292-9475; Gorder.1@osu.edu |