5 papers
Hard diagrams of split links
Corentin Lunel, Arnaud de Mesmay, Jonathan Spreer
Deformations of knots and links in ambient space can be studied combinatorially on their diagrams via local modifications called Reidemeister moves. While it is well-known that, in…
On the size of k-irreducible triangulations
Vincent Delecroix, Oscar Fontaine, Arnaud de Mesmay
A triangulation of a surface is k-irreducible if every non-contractible curve has length at least k and any edge contraction breaks this property. Equivalently, every edge belongs…
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…
Devil's Games and : Continuous Games complete for the First-Order Theory of the Reals
Lucas Meijer, Arnaud de Mesmay, Tillmann Miltzow +2
We introduce the complexity class Quantified Reals (). Let FOTR be the set of true sentences in the first-order theory of the reals. A language is in $\text…
Crossing numbers of dense graphs on surfaces
Alfredo Hubard, Arnaud de Mesmay, Hugo Parlier
In this paper, we provide upper and lower bounds on the crossing numbers of dense graphs on surfaces, which match up to constant factors. First, we prove that if is a dense eno…