If We Draw Graphs Like This, We Can Change Computers Forever

Jacob 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. Holm and Rotenberg were trying to find a shortcut for determining whether a graph is "planar"--that is, if it could be drawn flat on a surface without any of its lines crossing each other (flat drawings of a graph are also called "embeddings"). "Putting it very bluntly, we formally quantified why something is a terrible drawing." To mathematicians, a graph often looks different than what most of us are taught in school.