David Eppstein Wins Best Paper Award for ‘On the Biplanarity of Blowups’
At the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023), held from Sept. 20–23 in Palermo, Italy, David Eppstein’s paper “On the Biplanarity of Blowups” won the Best Paper award in the combinatorial and algorithmic aspects track. The conference has been the main hub for research into geometric representation and visualization of graphs and networks since its founding in 1992.
An Unsolved Problem
The paper is related to Ringel’s Earth–moon problem, a still-unsolved variation of the four-color problem posed by Gerhard Ringel in 1959. In this problem, countries on the Earth have space colonies on the moon, and the maps of the Earth and moon must be colored so that each country and its colony have the same color.
“Another different-looking but equivalent way of stating the same problem is: if a graph can be drawn in two layers in the plane, without any crossings within either layer, how many colors does it need?” says Eppstein, a Distinguished Professor of computer science in UC Irvine’s Donald Bren School of Information and Computer Sciences (ICS). “Although Ringel posed his question purely as a mathematical exercise, these two-layer drawings later gained practical applications in computer science, both in the design of computer circuitry — where the layers allow signals to cross each other as they connect components of the circuit — and as a way of visualizing networks that are too complicated to be drawn without crossings in a single layer.”
Ringel initially guessed that eight colors would be enough. However, in 1974, Thom Sulanke found a way of combining two simple graphs to produce an Earth–moon graph requiring nine colors. “Nothing worse has been found since, but the best we can prove is that 12 colors are always enough,” says Eppstein. “This kicked off a line of research asking for other ways of combining simpler graphs to produce graphs that could be represented by Earth–moon maps, or equivalently as two-layer drawings.” In a 2018 survey paper, Ellen Gethner conjectured that certain families of graphs could be represented by the adjacencies of countries and their colonies in Earth–moon maps.
Disproving Gethner’s Conjecture
Eppstein’s own interest in the subject of layered graph drawing began back in 1998, when he worked on a paper with UCI Professors Mike Dillencourt and Daniel Hirschberg. “We were motivated by the applications of these drawings in graph visualization and studied the question of whether allowing these drawings to have curved edges gave them more expressive power than forcing the edges to only be straight line segments,” he says. The answer was yes, and several of Eppstein’s subsequent papers continued this line of research.
Then, earlier this year, Eppstein noticed that Wikipedia was missing an article on the Earth–moon problem, so he decided to add one. “As one of the references for this new Wikipedia article, I used Gethner’s survey article, and while using it I found her conjecture in it,” he explains. “By applying some geometric ideas I had recently used in a different paper (a construction for building polyhedra by adding pyramids onto the faces of simpler polyhedra), I was able to disprove the conjecture.” This research is outlined in “On the Biplanarity of Blowups,” now an award-winning contribution to this work. Eppstein concludes in the paper that “2-blowups of iterated Kleetopes are not biplanar, but that 2-blowups of planar graphs with outer path decompositions are biplanar.” The paper then presents several open research questions for future work.
— Shani Murray