5 papers
A Discrete Analog of Tutte's Barycentric Embeddings on Surfaces
Ãric Colin de Verdière, Vincent Despré, Loïc Dubois
Tutte's celebrated barycentric embedding theorem describes a natural way to build straight-line embeddings (crossing-free drawings) of a (3-connected) planar graph: map the vertice…
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…
An FPT algorithm for the embeddability of graphs into two-dimensional simplicial complexes
Ãric Colin de Verdière, Thomas Magnard
We consider the embeddability problem of a graph G into a two-dimensional simplicial complex C: Given G and C, decide whether G admits a topological embedding into C. The problem i…
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…
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 encloses a set of k required objects in the plane while paying a penalty for enclosing unwanted…