campus scene
Pathmaster The math of graphs
Decoding the details Learning to read art
Unveiling the Middle East Lectures shed light on current turmoils
Thoroughbred legends cited Hall of Fame welcomes new stars
Sock it to me The secret life of T'bred laundry
Say what? Student polyglots
Books Faculty and alumni authors
Professoriat What the faculty are up to
Sportswrap Fall sports highlights
Pathmaster
Draw five dots, and add lines linking each to
every other without any lines crossing. Easy? Turns out
it’s impossible. Go ahead, try it—and come back when you give up. Skidmore mathematician Alice
Dean will wait for you.
She’ll even help you through every doomed
detour you attempt. And then
she’ll explain the arcane wisdoms (she
allows, “Sometimes it makes your brain hurt a little”) and common
joys of her research.
“I love solving puzzles,” she says, “especially those that no one else has figured out.” She’s solved her share of those, and published nearly twenty papers in professional journals, since joining the Skidmore faculty in 1986. Her specialty is graph theory, a study of networks
with complexes of nodes and connecting lines.
It’s used to plot postal delivery routes, microchip layouts, even the sorting and searching done by Google and its ilk.
The key is to devise algorithms for maximum efficiency. Take alphabetizing. Dean and her husband have a big collection of music on LPs, and she recently set about organizing them.
Rather than just
pick through the whole pile repeatedly, she used a simple informal algorithm: first she made three stacks—A–I, J–R, and S–Z—then sorted each into eight or nine substacks, one for each initial letter.
She admits, “I ran out of steam at that stage. All the As together, then all the Bs—that’s good enough.”
But consider a computer searching a 25,000entry phonebook listing. It could start at the top and look
at each name in order—potentially 25,000 steps if the desired name is at the end. Or it could turn to the exact middle
and see if that 12,500th name comes earlier or later in the alphabet than the target name.
In the half of the book now known to contain the target name, it again jumps to the halfway point and compares that entry, always breaking its sublist in half until it arrives at the right name. “We can figure how many comparisons this method takes,” says Dean, poking a calculator, “and it’s never more than…
sixteen. Compared
to 25,000, that’s a huge efficiency.”
Good algorithms are also crucial in planning networks, such as circuitry where wires can’t cross. Dean’s research often involves layouts, like the fivedot graph, that can’t be cleanly interlinked on one plane,
so they need either “thickness”—layers linked by one or more pins—or a 3D shape with “bridges” or “tubes.” Graph theory tackles other mindbogglers too, like groupings whose nodes connect to another group but not to each other, or colored nodes that can’t be placed adjacent to likecolored nodes. (A colleague once told Dean, “Ugh! Thickness is a swamp.”)
Lately Dean studies visibility graphs, where bars or rectangles are laid out so they can “see” each other; that is, no intervening rectangle fully blocks a “view” between them. Even if some boxes are drawn tall or wide, and even if they’re variously staggered on the page, complete visibility often can’t be achieved on one plane. Allowing a bar to see “through” one or more intervening bars gets Dean right back into
the thick of thickness.
Dean’s theorems and proofs can take months to work out, but it’s not solitary labor. “Graph theory is very social,” she says. “And maybe in part because it’s fairly new, it has more women than some areas
of math.” She regularly collaborates with farflung research partners by email, at conferences, even on hiking vacations. For the genial Dean—who came from workingclass roots and assumed grad school was out of reach until she learned of financial aid from an academic who picked her up hitchhiking—collegiality is a network of many links and lines of sight. —SR
