Untangling Planar Graphs

Abstract

Problems involving reconfigurations of geometric objects appear in all areas of science and engineering. Motivated by applications in gaming, we study reconfigurations of geometric graphs (that is, straight-line drawings of graphs with possibly lots of edge crossings). To untangle a geometric planar graph means to move some of its vertices so that the resulting geometric graph has no crossings. A popular on-line game, called, Planarity, asks a player to untangle a given geometric planar graph. The problem has also been studied in mathematical circles. We answer an open problem by Pach and Tardos [Discrete Comput. Geom., 2002] by providing the first polynomial lower bound for untangling geometric planar graphs.

Biographical Sketch

Vida Dujmovic is a research associate and an adjunct research professor at Carleton University in Ottawa, Canada. Her research interests lie in graph theory, graph drawing in particular, computational geometry and data structures. She received her Bachelor of Engineering from University of Zagreb, Zagreb, Croatia and her PhD from School of Computer Science at McGill University, Montreal, Canada.