top of page

Photo 10.05.22, 13 11 22.jpg

Sebastian Wiederrecht

I'm an Assistant Professor for Theoretical Computer Science at the School of Computing at KAIST in Daejeon, South Korea.

My main field of interest is (algorithmic) structural graph theory.

Here you can find my CV.

(last updated November 2023)

The Graph Minor Structure Theorem, originally proven by Robertson and Seymour [JCTB, 2003], asserts that there exist functions f_1 and f_2 such that for every non-planar graph H with t=|V(H)|, every H-minor-free graph can be obtained via the clique-sum operation from graphs which embed into surfaces where H does not embed after deleting at most f_1(t) many vertices with up to at most t^2-1 many ``vortices'' which are of ``depth'' at most f_2(t). In the proof presented by Robertson and Seymour the functions f_1 and f_2 are non-constructive. Kawarabayashi, Thomas, and Wollan [arXiv, 2020] found a new proof showing that f_1(t), f_2(t) = 2^{poly(t)}. While believing that this bound was the best their methods could achieve, Kawarabayashi, Thomas, and Wollan conjectured that f_1 and f_2 can be improved to be polynomials.
In this paper we confirm their conjecture and prove that f_1(t),f_2(t) = O(t^{2300}). Our proofs are fully constructive and yield a polynomial-time algorithm that either finds H as a minor in a graph G or produces a clique-sum decomposition for G as above.

bottom of page