Mathematics Computer Science Seminar
UIC, Department of Computer Science
Approximation algorithms for graph planarization and related problems
Abstract: Some central problems in topological graph theory concern the computation of parameters such as the crossing number, Euler genus, and planarization number of a given graph. When the value of this parameter, k, is a fixed constant, polynomial-time algorithms can be obtained using tools and ideas that originated in the graph minor theory. However, since computing any of these parameters is NP-hard, the resulting algorithms are efficient only for very small values of k. We present some recent results that bypass this obstacle by giving approximation algorithms for several of these problems. Based mostly on joint works with Chandra Chekuri, and Ken-ichi Kawarabayashi.
Monday October 30, 2017 at 10:00 AM in SEO 612