Arnaud de Mesmay

According to our database, Arnaud de Mesmay authored at least 40 papers between 2011 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Crossing numbers of dense graphs on surfaces.

Alfredo Hubard, Arnaud de Mesmay, Hugo Parlier

CoRR, June, 2025

Hard Diagrams of Split Links.

Corentin Lunel, Arnaud de Mesmay, Jonathan Spreer

Proceedings of the 41st International Symposium on Computational Geometry, 2025

2024

Hard Diagrams of the Unknot.

Benjamin A. Burton, Hsien-Chih Chang, Maarten Löffler, Clément Maria, Arnaud de Mesmay, Saul Schleimer, Eric Sedgwick, Jonathan Spreer

Exp. Math., July, 2024

Representing Matroids over the Reals is ∃ℝ-complete.

Eun Jung Kim, Arnaud de Mesmay, Tillmann Miltzow

Discret. Math. Theor. Comput. Sci., 2024

Triangulations in Geometry and Topology (Dagstuhl Seminar 24072).

Maike Buchin, Jean Cardinal, Arnaud de Mesmay, Jonathan Spreer, Alex He

Dagstuhl Reports, 2024

A PTAS for <i>ℓ</i>₀-Low Rank Approximation: Solving Dense CSPs over Reals.

Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Hopf Arborescent Links, Minor Theory, and Decidability of the Genus Defect.

Pierre Dehornoy, Corentin Lunel, Arnaud de Mesmay

Proceedings of the 40th International Symposium on Computational Geometry, 2024

2023

A PTAS for 𝓁₀-Low Rank Approximation: Solving Dense CSPs over Reals.

Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang

CoRR, 2023

Voting algorithms for unique games on complete graphs.

Antoine Méot, Arnaud de Mesmay, Moritz Mühlenthaler, Alantha Newman

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Degenerate Crossing Number and Signed Reversal Distance.

Niloufar Fuladi, Alfredo Hubard, Arnaud de Mesmay

Proceedings of the Graph Drawing and Network Visualization - 31st International Symposium, 2023

A Structural Approach to Tree Decompositions of Knots and Spatial Graphs.

Corentin Lunel, Arnaud de Mesmay

Proceedings of the 39th International Symposium on Computational Geometry, 2023

2022

Computation and Reconfiguration in Low-Dimensional Topological Spaces (Dagstuhl Seminar 22062).

Maike Buchin, Anna Lubiw, Arnaud de Mesmay, Saul Schleimer

Dagstuhl Reports, 2022

Fitting Metrics and Ultrametrics with Minimum Disagreements.

Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, Arnaud de Mesmay

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Short Topological Decompositions of Non-Orientable Surfaces.

Niloufar Fuladi, Alfredo Hubard, Arnaud de Mesmay

Proceedings of the 38th International Symposium on Computational Geometry, 2022

Finding Weakly Simple Closed Quasigeodesics on Polyhedral Spheres.

Jean Chartier, Arnaud de Mesmay

Proceedings of the 38th International Symposium on Computational Geometry, 2022

Interactions between algorithms, geometry and topology in low dimensions. (Interactions entre les algorithmes, la géométrie et la topologie en basse dimension).

Arnaud de Mesmay

, 2022

2021

Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries.

Erin Wolf Chambers, Francis Lazarus, Arnaud de Mesmay, Salman Parsa

Proceedings of the 37th International Symposium on Computational Geometry, 2021

Distributed Coloring and the Local Structure of Unit-Disk Graphs.

Louis Esperet, Sébastien Julliot, Arnaud de Mesmay

Proceedings of the Algorithms for Sensor Systems, 2021

2020

Tightening Curves on Surfaces Monotonically with Applications.

Hsien-Chih Chang, Arnaud de Mesmay

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

On the tree-width of knot diagrams.

Saul Schleimer, Arnaud de Mesmay, Jessica S. Purcell, Eric Sedgwick

J. Comput. Geom., 2019

Link Crossing Number is NP-hard.

Arnaud de Mesmay, Marcus Schaefer, Eric Sedgwick

CoRR, 2019

Homotopy Height, Grid-Major Height and Graph-Drawing Height.

Therese Biedl, Erin Wolf Chambers, David Eppstein, Arnaud de Mesmay, Tim Ophelders

Proceedings of the Graph Drawing and Network Visualization - 27th International Symposium, 2019

The Unbearable Hardness of Unknotting.

Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick, Martin Tancer

Proceedings of the 35th International Symposium on Computational Geometry, 2019

Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs.

Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, Arnaud de Mesmay

Proceedings of the 35th International Symposium on Computational Geometry, 2019

2018

Embeddability in ℝ³ is NP-hard.

Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick, Martin Tancer

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

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

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

The Bane of Low-Dimensionality Clustering.

Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg, Alan Roytman

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Tightening Curves on Surfaces via Local Moves.

Hsien-Chih Chang, Jeff Erickson, David Letscher, Arnaud de Mesmay, Saul Schleimer, Eric Sedgwick, Dylan Thurston, Stephan Tillmann

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

On the complexity of optimal homotopies.

Erin Wolf Chambers, Arnaud de Mesmay, Tim Ophelders

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2016

Shortest Path Embeddings of Graphs on Surfaces.

Alfredo Hubard, Vojtech Kaluza, Arnaud de Mesmay, Martin Tancer

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

Finding Non-Orientable Surfaces in 3-Manifolds.

Benjamin A. Burton, Arnaud de Mesmay, Uli Wagner

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015

A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface.

Vincent Cohen-Addad, Arnaud de Mesmay

Proceedings of the Algorithms - ESA 2015, 2015

2014

Topics in Low-Dimensional Computational Topology. (Problèmes de topologie algorithmique en basse dimension).

Arnaud de Mesmay

PhD thesis, 2014

Testing Graph Isotopy on Surfaces.

Éric Colin de Verdière, Arnaud de Mesmay

Discret. Comput. Geom., 2014

On the Complexity of Immersed Normal Surfaces.

Benjamin A. Burton, Éric Colin de Verdière, Arnaud de Mesmay

CoRR, 2014

Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces.

Éric Colin de Verdière, Alfredo Hubard, Arnaud de Mesmay

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013

Dimension Reduction for Finite Trees in ℓ 1.

James R. Lee, Arnaud de Mesmay, Mohammad Moharrami

Discret. Comput. Geom., 2013

2012

Dimension reduction for finite trees in <i>l</i>₁.

James R. Lee, Arnaud de Mesmay, Mohammad Moharrami

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Testing graph isotopies on surfaces.

Arnaud de Mesmay, Éric Colin de Verdière

Proceedings of the 28th ACM Symposium on Computational Geometry, 2012

2011

Dimension reduction for finite trees in L_1

James R. Lee, Arnaud de Mesmay, Mohammad Moharrami

CoRR, 2011