The notion of 1-planarity is among the most natural and most studied generalizations of
graph planarity. A graph is 1-planar if it has an embedding where each edge is crossed by at …

We give the first polynomial-time approximation schemes (PTASs) for the following
problems:(1) uniform facility location in edge-weighted planar graphs;(2) k-median and k …

We give an algorithmic and lower bound framework that facilitates the construction of
subexponential algorithms and matching conditional complexity bounds. It can be applied to …

The planar graph product structure theorem of Dujmović et al.[J. ACM, 67 (2020), 22] states
that every planar graph is a subgraph of the strong product of a graph with bounded …

We introduce tensor network contraction algorithms for counting satisfying assignments of
constraint satisfaction problems (# CSPs). We represent each arbitrary# CSP formula as a …

We study exact algorithms for Euclidean TSP in R d. In the early 1990s algorithms with n O
(√ n) running time were presented for the planar case, and some years later an algorithm …

We initiate a systematic study of approximation schemes for fundamental optimization
problems on disk graphs, a common generalization of both planar graphs and unit-disk …

Under the Strong Exponential-Time Hypothesis, the diameter of general unweighted graphs
cannot be computed in truly subquadratic time. Nevertheless there are several graph …

Let F be a set of n objects in the plane and let G×(F) be its intersection graph. A balanced
clique-based separator of G×(F) is a set S consisting of cliques whose removal partitions …

For α>1, an α-approximate (bi) kernel is a polynomial-time algorithm that takes as input an
instance (I,k) of a problem Q and outputs an instance (I',k') (of a problem Q') of size bounded …