Tomáš Masařík, Separator Theorem for Minor-free Graphs in Linear Time
Room B332 IBS (기초과학연구원)The planar separator theorem by Lipton and Tarjan states that any planar graph with $n$ vertices has a balanced separator of size $O(\sqrt{n})$ that can be found in linear time. This landmark result kicked off decades of research on designing linear or nearly linear-time algorithms on planar graphs. In an attempt to generalize Lipton-Tarjan's theorem …