research
∙
08/21/2023
Degenerate crossing number and signed reversal distance
The degenerate crossing number of a graph is the minimum number of trans...
share
research
∙
03/14/2023
A Structural Approach to Tree Decompositions of Knots and Spatial Graphs
Knots are commonly represented and manipulated via diagrams, which are d...
research
∙
01/09/2023
Representing Matroids over the Reals is ∃ℝ-complete
A matroid M is an ordered pair (E,I), where E is a finite set called the...
research
∙
08/29/2022
Fitting Metrics and Ultrametrics with Minimum Disagreements
Given x ∈ (ℝ_≥ 0)^[n]2 recording pairwise distances, the METRIC VIOLATIO...
research
∙
03/13/2022
Short Topological Decompositions of Non-Orientable Surfaces
In this article, we investigate short topological decompositions of non-...
research
∙
03/11/2022
Finding Weakly Simple Closed Quasigeodesics on Polyhedral Spheres
A closed quasigeodesic on a convex polyhedron is a closed curve that is ...
research
∙
10/22/2021
Voting algorithms for unique games on complete graphs
An approximation algorithm for a Constraint Satisfaction Problem is call...
research
∙
06/23/2021
Distributed coloring and the local structure of unit-disk graphs
Coloring unit-disk graphs efficiently is an important problem in the glo...
research
∙
12/04/2020
Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries
In this paper we prove that the problem of deciding contractibility of a...
research
∙
03/02/2020
Tightening Curves on Surfaces Monotonically with Applications
We prove the first polynomial bound on the number of monotonic homotopy ...
research
∙
08/15/2019
Homotopy height, grid-major height and graph-drawing height
It is well-known that both the pathwidth and the outer-planarity of a gr...
research
∙
08/12/2019
Link Crossing Number is NP-hard
We show that determining the crossing number of a link is NP-hard. For s...
research
∙
03/20/2019
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
We prove essentially tight lower bounds, conditionally to the Exponentia...
research
∙
11/03/2017
The Bane of Low-Dimensionality Clustering
In this paper, we give a conditional lower bound of n^Ω(k) on running ti...
research
∙
11/02/2017
On the complexity of optimal homotopies
In this article, we provide new structural results and algorithms for th...
research
∙
08/25/2017