School Seminars and Colloquia

Untangling Planar Graphs

Discrete Structures and Algorithms (Seminar)

by Vida Dujmovic

Institution: Carleton University, Ottawa, Canada
Date: Tue 18th October 2011
Time: 11:00 AM
Location: Russell Love Theatre, Richard Berry Building

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.