6 citations · 10 across the 12 of their papers we have counts for
15 papers
Degenerate crossing number and signed reversal distance
Niloufar Fuladi, Alfredo Hubard, Arnaud de Mesmay
Given a graph drawn in the plane, the degenerate crossing number of the drawing is the number of points in the plane which are contained in the relative interior of at least two ed…
A Structural Approach to Tree Decompositions of Knots and Spatial Graphs
Corentin Lunel, Arnaud de Mesmay
Knots are commonly represented and manipulated via diagrams, which are decorated planar graphs. When such a knot diagram has low treewidth, parameterized graph algorithms can be le…
Universal families of arcs and curves on surfaces
Niloufar Fuladi, Arnaud de Mesmay, Hugo Parlier
The main goal of this paper is to investigate the minimal size of families of curves on surfaces with the following property: a family of simple closed curves on a surface real…
Representing Matroids over the Reals is -complete
Eun Jung Kim, Arnaud de Mesmay, Tillmann Miltzow
A matroid is an ordered pair , where is a finite set called the ground set and a collection called the independent sets which satisfy the conditions…
Fitting Metrics and Ultrametrics with Minimum Disagreements
Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee +1
Given recording pairwise distances, the METRIC VIOLATION DISTANCE (MVD) problem asks to compute the distance between and…
Finding Weakly Simple Closed Quasigeodesics on Polyhedral Spheres
Jean Chartier, Arnaud de Mesmay
A closed quasigeodesic on a convex polyhedron is a closed curve that is locally straight outside of the vertices, where it forms an angle at most on both sides. While the exist…
Voting algorithms for unique games on complete graphs
Antoine Méot, Arnaud de Mesmay, Moritz Mühlenthaler +1
An approximation algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying a -fraction of the constraints on any -s…
Distributed coloring and the local structure of unit-disk graphs
Louis Esperet, Sébastien Julliot, Arnaud de Mesmay
Coloring unit-disk graphs efficiently is an important problem in the global and distributed setting, with applications in radio channel assignment problems when the communication r…
Embeddability in is NP-hard
Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick +1
We prove that the problem of deciding whether a 2- or 3-dimensional simplicial complex embeds into is NP-hard. Our construction also shows that deciding whether a 3-…
Constructing monotone homotopies and sweepouts
Erin Wolf Chambers, Gregory R. Chambers, Arnaud de Mesmay +2
This article investigates when homotopies can be converted to monotone homotopies without increasing the lengths of curves. A monotone homotopy is one which consists of curves whic…
A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals
Vincent Cohen-Addad, Éric Colin de Verdière, Arnaud de Mesmay
For an undirected edge-weighted graph and a set of pairs of vertices called pairs of terminals, a multicut is a set of edges such that removing these edges from disconn…
Finding non-orientable surfaces in 3-manifolds
Benjamin A. Burton, Arnaud de Mesmay, Uli Wagner
We investigate the complexity of finding an embedded non-orientable surface of Euler genus in a triangulated -manifold. This problem occurs both as a natural question in low…
On the Complexity of Immersed Normal Surfaces
Benjamin A. Burton, Éric Colin de Verdière, Arnaud de Mesmay
Normal surface theory, a tool to represent surfaces in a triangulated 3-manifold combinatorially, is ubiquitous in computational 3-manifold theory. In this paper, we investigate a…
Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces
Éric Colin de Verdière, Alfredo Hubard, Arnaud de Mesmay
How much cutting is needed to simplify the topology of a surface? We provide bounds for several instances of this question, for the minimum length of topologically non-trivial clos…
Dimension reduction for finite trees in L_1
James R. Lee, Arnaud de Mesmay, Mohammad Moharrami
We show that every n-point tree metric admits a (1+eps)-embedding into a C(eps) log n-dimensional L_1 space, for every eps > 0, where C(eps) = O((1/eps)^4 log(1/eps)). This matches…