Zobrazeno 1 - 10
of 54
pro vyhledávání: '"de Verdière, Éric Colin"'
Autor:
de Verdière, Éric Colin, Hliněný, Petr
The basic crossing number problem is to determine the minimum number of crossings in a topological drawing of an input graph in the plane. In this paper, we develop fixed-parameter tractable (FPT) algorithms for various generalized crossing number pr
Externí odkaz:
http://arxiv.org/abs/2410.00206
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, any two non-separating simple closed curves are related by a self-homeo
Externí odkaz:
http://arxiv.org/abs/2403.11749
Consider a graph drawn on a surface (for example, the plane minus a finite set of obstacle points), possibly with crossings. We provide an algorithm to decide whether such a drawing can be untangled, namely, if one can slide the vertices and edges of
Externí odkaz:
http://arxiv.org/abs/2311.00437
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 is NP-hard, even in the restricted case where C is homeomorphic to a su
Externí odkaz:
http://arxiv.org/abs/2107.06236
Autor:
de Verdière, Éric Colin, Parsa, Salman
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 contractible in M. Our algorithm runs in space polynomial in the size of
Externí odkaz:
http://arxiv.org/abs/2001.04747
Publikováno v:
Theoretical Computer Science 835 (2020) 120-133
In the Minimum Installation Path problem, we are given a graph $G$ with edge weights $w(.)$ and two vertices $s,t$ of $G$. We want to assign a non-negative power $p(v)$ to each vertex $v$ of $G$ so that the edges $uv$ such that $p(u)+p(v)$ is at leas
Externí odkaz:
http://arxiv.org/abs/1910.04228
We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem. A cu
Externí odkaz:
http://arxiv.org/abs/1903.08603
We consider the problem of deciding whether an input graph G admits a topological embedding into a two-dimensional simplicial complex C. This problem includes, among others, the embeddability problem of a graph on a surface and the topological crossi
Externí odkaz:
http://arxiv.org/abs/1803.07032
Autor:
COHEN-ADDAD, VINCENT1 vcohenad@gmail.com, DE VERDIÈRE, ÉRIC COLIN2 eric.colindeverdiere@u-pem.fr, MARX, DÁNIEL3 ademesmay@gmail.com, DE MESMAY, ARNAUD2 marx@cispa.de
Publikováno v:
Journal of the ACM. Jul2021, Vol. 68 Issue 4, p1-26. 26p.
A pseudocircle is a simple closed curve on some surface; an arrangement of pseudocircles is a collection of pseudocircles that pairwise intersect in exactly two points, at which they cross. Ortner proved that an arrangement of pseudocircles is embedd
Externí odkaz:
http://arxiv.org/abs/1704.07688