1 citations · 2 across the 7 of their papers we have counts for
8 papers
Finding a Shortest Curve that Separates Few Objects from Many
Therese Biedl, Éric Colin de Verdière, Fabrizio Frati +2
We present a fixed-parameter tractable (FPT) algorithm to find a shortest curve that separates some polygons from others. Formally, the input is a set of interior-disjoint simple p…
A Unified FPT Framework for Crossing Number Problems
Éric Colin de Verdière, Petr Hliněný
The basic (and traditional) crossing number problem is to determine the minimum number of crossings in a topological drawing of an input graph in the plane. We develop a unified fr…
Computing shortest closed curves on non-orientable surfaces
Denys Bulavka, Éric Colin de Verdière, Niloufar Fuladi
We initiate the study of computing shortest non-separating simple closed curves with some given topological properties on non-orientable surfaces. While, for orientable surfaces, a…
Deciding contractibility of a non-simple curve on the boundary of a 3-manifold: A computational Loop Theorem
Éric Colin de Verdière, Salman Parsa
We present an algorithm for the following problem. Given a triangulated 3-manifold M and a (possibly non-simple) closed curve on the boundary of M, decide whether this curve is con…
Hardness of Minimum Barrier Shrinkage and Minimum Installation Path
Sergio Cabello, Éric Colin de Verdière
In the Minimum Installation Path problem, we are given a graph with edge weights and two vertices of . We want to assign a non-negative power to each ver…
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…