Mathematics Computer Science Seminar
Anastasios Sidiropoulos
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