24 March/April 2021
Deep Math
8
// BY SARAH WELLS //If We Draw
Graphs Like
This, We Can
Change
Computers
In electronics
design, graphs
must be planar,
meaning you
can draw them
on a flat surface
without crossing
any lines.J
ACOB HOLM WAS FLIPPING THROUGH
proofs from an October 2019 research
paper he and colleague Eva Rotenberg—
an associate professor in the department
of applied mathematics and computer
science at the Technical University of
Denmark—had published online, when
he discovered their findings had unwittingly given
away a solution to a centuries-old graph problem.
Holm, an assistant professor of computer
science at the University of Copenhagen, was
relieved no one had caught the solution first. “It
was a real ‘Eureka!’ moment,” he says. “It suddenly
seemed obvious.”
Holm and Rotenberg were trying to find a
shortcut for determining whether a graph is “pla-
nar”—that is, if it could be drawn f lat on a surface
without any of its lines crossing each other (f lat
drawings of a graph are also called “embeddings”).
To mathematicians, a graph often looks dif-
ferent than what most of us are taught in school.
A graph in this case is any number of points,
called nodes, connected by pairwise relations,
called edges. In other words, an edge is a curve
that connects two nodes. Under this definition,
a graph can represent anything from the com-
plex wiring inside a computer chip to a road map
of a city, in which the streets of Manhattan could
be represented as edges, and their intersections
represented as nodes. The study of such graphs is
called graph theory.
Engineers need to find planarity in a graph
when, for example, they are designing a computer
chip without a crossed wire. But assessing for pla-
narity amid the addition and removal of edges
is difficult without drawing the graph yourself
and trying not to cross any lines. You can expe-
rience this precise challenge with a brain teaser
called “The Three Utilities Problem,” published
in an issue of The Strand Magazine in 1913 (see
sidebar).
Assessing for planarity becomes even more
complicated in larger graphs with lots of nodes
and edges, says Rotenberg. This is a real-world
issue. Quantum computer chips, for instance, are
highly advanced, and finding efficient ways to
assess their planarity without wasting time and
money is crucial to their development.
In their original 2019 paper published on the
preprint server arXiv—where research often first