Showing 2019Show all
2 papers · 1 filter
cs.CG2019
Link Crossing Number is NP-hard
Arnaud de Mesmay, Marcus Schaefer, Eric Sedgwick
We show that determining the crossing number of a link is NP-hard. For some weaker notions of link equivalence, we also show NP-completeness.
cs.CC2019
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…