26 March/April 2021
Deep Math
8sees the light of day before peer review—Holm and
Rotenberg classified a type of embedding called a
“ba lanced” or “good” embedding.
Holm explains that these good embeddings
“tend to ‘balance’ the [time] costs of inserting
edges so that no possible edge insertion costs too
much compared to the rest.” This is a concept
borrowed for balanced decision trees in computer
science, which are designed with evenly dispersed
branches for minimized search time. Put another
way, good embeddings are easier to add new edges
to without violating planarity.
If you were to look at it, Holm says, a “good”
embedding would be simple, unconvoluted. The
standard example is the so-called Ladder Graph.
A balanced embedding of this graph looks exactly
like a ladder. But Holm says: “In an unbalanced
embedding, it is hardly recognizable.”
It seems subjective to say the Ladder Graph is
“good” and its alternatives are “bad,” but Holm
and Rotenberg articulated in their paper why
those statements were mathematically true. “Put-
ting it very bluntly, we formally quantified why
something is a terrible drawing,” says Rotenberg,
referring to a bad embedding. What the pair didn’t
realize at the time was that their class of good
embeddings played an essential role in speeding
up the process of dynamic planarity testing.
When adding a new edge to a planar graph
is required, there are two scenarios: There is a
safe way to add the edge, possibly after modify-
ing the drawing, or no drawing admitting the
edge exists. But in some cases, the embedding of
a graph itself might be disguising a way the edge
could be inserted in planar fashion. To reveal
those alternative paths, mathematicians “f lip”
an embedding to change its orientation while
keeping it mathematically identical, because the
relationship between the connected nodes and
edges hasn’t changed.
These f lips might make it possible to add edges
between two newly arranged nodes, edges that
would have otherwise violated planarity. Holm
and Rotenberg discovered the f lips that lead to
successful edge insertion and deletion tended
to fall into their class of so-called good embed-
dings. Similarly, these good embeddings require
fewer f lips overall to successfully add new edges.
A win-win.
The pair have suggested numerous applica-
tions for their work, including chip design, surface
meshes, and road networks, but Rotenberg has
admitted: “What attracts us to this problem is
its puzzle-like nature.” The two are cautious to
predict more commercial applications because
completing “f lips” in real-world graph designs
can be challenging.
However, they say that their approach to assess-
ing dynamic graphs (i.e., graphs that change
via insertions and deletions) could impact how
mathematicians approach similar problems.
Essentially, while their algorithm assesses pla-
narity, it also tracks and calculates changes to
the graphs, performing what is called a “recourse
analysis,” says Rotenberg.
But such data gathering isn’t superf luous. Roten-
berg argues their solution shows that recourse
analysis could have algorithmic applications in
addition to being “interesting in its own right,”
because here, it led to their efficient planarity test.
Analyzing dynamic mathematical concepts
is an “open field,” she says, but therein lies the
potential. The breakthroughs might have already
happened—they’re just hidden in the process.Can You Solve the Three Utilities Problem?
These three houses each need access to water, gas, and electricity—but for safety
reasons the lines connecting the utilities and houses cannot cross. Grab a sheet
of paper, draw out this scenario, and try to connect all three houses to all three
utilities without any two lines crossing. Check the solution below when you think
you have the right answer.
Solution: It’s actually impossible in two-dimensional space.