Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs

Vincent Cohen-Addad, Éric Colin de Verdière, Daniel Marx +1

We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded gra…