Given an unweighted graph G, the minimum r-dominating set problem asks for a subset of vertices S of the smallest cardinality, such that every vertex in G is within radius r to some vertex in S. While the r-dominating set problem on planar graph admits PTAS from Baker’s shifting/layering technique when r is a constant, the problem becomes significantly harder when r can depend on n. In fact, under Exponential-Time Hypothesis, Fox-Epstein ηl [SODA 2019] observed that no efficient PTAS can exist for the unbounded r-dominating set problem on planar graphs. One may consider even harder weighted-variant known as the vertex-weighted metric r-dominating set, where edges are associated with lengths, and every vertex is associated with a positive-valued weight, and the goal is to compute an r-dominating set with minimum total weight. As a result, people resorted to bicriteria algorithms by allowing the returned solution to use radius-(1+ε)r balls instead, in addition to the total weight being a 1+ε approximation to the optimal value. We establish the first single-criteria polynomial-time O(1)-approximation algorithm for the vertex-weighted metric r-dominating set problem on planar graphs when r is part of the input, and can be arbitrarily large compared to n. Our new (single-criteria) O(1)-approximation algorithm uses the quasi-uniformity sampling technique of Chan et al. [SODA 2012] by bounding the shallow cell complexity of the (unbounded) radius-r ball system to be linear in n. To this end we have two technical innovations: 1) The discrete ball system on planar graphs are neither pseudodisks nor have well-defined boundaries for standard union-complexity arguments. We construct a support graph for arbitrary distance ball systems as contractions of Voronoi cells; the sparseness comes as a byproduct. 2) We present an assignment of each depth-(≥3) cell to a unique 3-tuple of ball centers. This allows us to use standard Clarkson-Shor techniques to reduce the counting to cells of depth exactly 3, which we prove to be size O(n) by a novel geometric argument based on our support being a Voronoi contraction.

Recent research on computing the diameter of geometric intersection graphs has made significant strides, primarily focusing on the 2D case [Duraj et al., 2024; Hsien-Chih Chang et al., 2024; Chan et al., 2025] where truly subquadratic-time algorithms were given for simple objects such as unit-disks and (axis-aligned) squares. However, in three or higher dimensions, there is no known truly subquadratic-time algorithm for any intersection graph of non-trivial objects, even basic ones such as unit balls or (axis-aligned) unit cubes. This was partially explained by the pioneering work of Bringmann et al. [Karl Bringmann et al., 2022] which gave several truly subquadratic lower bounds, notably for unit balls or unit cubes in 3D when the graph diameter Δ is at least Ω(log n), hinting at a pessimistic outlook for the complexity of the diameter problem in higher dimensions. In this paper, we substantially extend the landscape of diameter computation for objects in three and higher dimensions, giving a few positive results. Our highlighted findings include: 1) A truly subquadratic-time algorithm for deciding if the diameter of unit cubes in 3D is at most 3 (Diameter-3 hereafter), the first algorithm of its kind for objects in 3D or higher dimensions. Our algorithm is based on a novel connection to pseudolines, which is of independent interest. 2) A truly subquadratic time lower bound for Diameter-3 of unit balls in 3D under the Orthogonal Vector (OV) hypothesis, giving the first separation between unit balls and unit cubes in the small diameter regime. Previously, computing the diameter for both objects was known to be quadratic hard when the diameter is Ω(log n) [Karl Bringmann et al., 2022]. 3) A near-linear-time algorithm for Diameter-2 of unit cubes in 3D, generalizing the previous result for unit squares in 2D [Karl Bringmann et al., 2022]. 4) A truly subquadratic-time algorithm and lower bound for Diameter-2 and Diameter-3 of rectangular boxes (of arbitrary dimension and sizes), respectively.

Given a weighted digraph G, a (t,g,μ)-DAG cover is a collection of g dominating DAGs D_1,… ,D_g such that all distances are approximately preserved: for every pair (u,v) of vertices, min_id_{D_i}(u,v) ≤ t⋅ d_G(u,v), and the total number of non-G edges is bounded by |(∪_i D_i)⧵ G| ≤ μ. Assadi, Hoppenworth, and Wein [STOC 25] and Filtser [SODA 26] studied DAG covers for general digraphs. This paper initiates the study of Steiner DAG cover, where the DAGs are allowed to contain Steiner points. We obtain Steiner DAG covers on the important classes of planar digraphs and low-treewidth digraphs. Specifically, we show that any digraph with treewidth tw admits a (1,2,Õ(n⋅tw))-Steiner DAG cover. For planar digraphs we provide a (1+ε,2,Õ_ε(n))-Steiner DAG cover. We also demonstrate a stark difference between Steiner and non-Steiner DAG covers. As a lower bound, we show that any non-Steiner DAG cover for graphs with treewidth 1 with stretch t < 2 and sub-quadratic number of extra edges requires Ω(log n) DAGs.

Computing the diameter of the intersection graphs of objects is a basic problem in computational geometry. Previous works showed that the complexity of computing the diameter mainly depends on the object types: for unit disks and squares in 2D, the problem is solvable in truly subquadratic time [Chan et al., 2025], while for other objects, including unit segments and equilateral triangles in 2D or unit balls and axis-parallel unit cubes in 3D, there is no truly subquadratic time algorithm under the Orthogonal Vector (OV) hypothesis [Bringmann et al., 2022]. We undertake a comprehensive study of computing the diameter of geometric intersection graphs for various types of objects. We discover many new irregularities, showing that the landscape is extremely nuanced: the source of hardness is a combination of the object type, the true diameter value, and how the objects intersect with each other. Our highlighted results for the 2D case include: 1) The diameter of non-degenerate, axis-aligned line segments can be computed in truly subquadratic time. Previous hardness result [Bringmann et al., 2022] for line segments applies only to degenerate instances. On the other hand, for the degenerate case, we show that a truly subquadratic time algorithm exists when the true diameter is constant. 2) An almost-linear-time algorithm for unit-square graphs of constant diameter. Previous algorithms [Duraj et al., 2024; Chan et al., 2025] rely on succinct representation assuming bounded VC-dimension; for such a strategy Ω(n^{7/4}) time is an inherent barrier. 3) An Õ(n^{4/3})-time algorithm to decide if the diameter of a unit-disk graph is at most 2. This improves upon the recent algorithm with running time Õ(n^{2-1/9}) [Chan et al., 2025]. 4) Deciding if the diameter of intersection graphs of fat triangles or line segments is at most 2 is truly subquadratic-hard under fine-grained complexity assumptions. Previous lower bounds [Bringmann et al., 2022] only hold when deciding if diameter is at most 3. Our findings are presented in a pair of papers. This paper focuses solely on the 2D case, while the companion paper is devoted to higher-dimensional cases.

We give the first truly subquadratic time algorithm, with ${O^{\ast}}\left( {{n^{2 - 1/18}}} \right)$ running time, for computing the diameter of an n-vertex unit-disk graph, resolving a central open problem in the literature. Our result is obtained as an instance of a general framework, applicable to different graph families and distance problems. Surprisingly, our framework completely bypasses sublinear separators (or r-divisions) which were used in all previous algorithms. Instead, we use low-diameter decompositions in their most elementary form. We also exploit bounded VC-dimension of set systems associated with the input graph, as well as new ideas on geometric data structures. Among the numerous applications of the general framework, we obtain:1)An $\tilde O\left( {m{n^{1 - 1/(2d)}}} \right)$ time algorithm for computing the diameter of m-edge sparse unweighted graphs with constant VC-dimension d. The previously known algorithms by Ducoffe, Habib, and Viennot [SODA 2019] and Duraj, Konieczny, and Potępa [ESA 2024] are truly subquadratic only when the diameter is a small polynomial. Our result thus generalizes truly subquadratic time algorithms known for planar and minor-free graphs (in fact, it slightly improves the previous time bound for minor-free graphs).2)An $\tilde O\left( {{n^{2 - 1/12}}} \right)$ time algorithm for computing the diameter of intersection graphs of axis-aligned squares with arbitrary size. The best-known algorithm by Duraj, Konieczny, and Potępa [ESA 2024] only works for unit squares and is only truly subquadratic in the low-diameter regime.3)The first algorithms with truly subquadratic complexity for other distance-related problems, including all-vertex eccentricities, Wiener index, and exact distance oracles. In particular, we obtain the first exact distance oracle with truly subquadratic space and $\tilde O(1)$ query time for any sparse graph with bounded VC-dimension, again generalizing previous results for planar and minor-free graphs.

Given an edge-weighted graph G and a subset of vertices T called terminals, an $\alpha$-distance-approximating minor ($\alpha$-DAM) of G is a graph minor H of G that contains all terminals, such that the distance between every pair of terminals is preserved up to a factor of $\alpha$. Distance-approximating minor would be an effective distance-sketching structure on minor-closed family of graphs; in the constant-stretch regime it generalizes the well-known Steiner Point Removal problem by allowing the existence of (a small number of) non-terminal vertices. Unfortunately, in the ($1+\varepsilon$) regime the only known DAM construction for planar graphs relies on overlaying $\tilde{O}_{\varepsilon}(|T|)$ shortest paths in G, which naturally leads to a quadratic bound in the number of terminals [Cheung, Goranci, and Henzinger, ICALP 2016]. We break the quadratic barrier and build the first ($1+\varepsilon$)-distance-approximating minor for k-terminal planar graphs and minor-free graphs of near-linear size $\tilde{O}_{\varepsilon}(k)$. In addition to the near-optimality in size, the construction relies only on the existence of shortest-path separators [Abraham and Gavoille, PODC 2006] and $\varepsilon$-covers [Thorup, J. ACM 2004]. Consequently, this provides an alternative and simpler construction to the near-linear-size emulator for planar graphs [Chang, Krauthgamer, and Tan, STOC 2022], as well as the first near-linear-size emulator for minor-free graphs. Our DAM can be constructed in near-linear time.

We study reconfiguration in curve arrangements, where a subset of the crossings are marked as switches which have three possible states, and the goal is to set the switches such that the resulting curve arrangement has few self-intersections, or few faces that are incident to the same curve multiple times (a.k.a. popular faces). Our results are that these problems are NP-hard, but FPT in the number of switches. Minimizing self-intersections is also FPT in the number of non-switchable crossings; for minimizing popular faces this problem remains open. Our results can be applied to generating curved nonograms, a type of logic puzzle that has received some attention lately. Specifically, our results make it possible to efficiently convert expert puzzles into advanced puzzles (or determine that this is impossible).

Cohen-Addad, Le, Pilipczuk, and Pilipczuk [CLPP23] recently constructed a stochastic embedding with expected 1 + ε distortion of n-vertex planar graphs (with polynomial aspect ratio) into graphs of treewidth O (ε-1 log13n ). Their embedding is the first to achieve polylogarithmic treewidth. However, there remains a large gap between the treewidth of their embedding and the treewidth lower bound of Ω(log n ) shown by Carroll and Goel [CG04]. In this work, we substantially narrow the gap by constructing a stochastic embedding with treewidth O (ε-1 log3 n ).

Finding the diameter of a graph in general cannot be done in truly subquadratic assuming the Strong Exponential Time Hypothesis (SETH), even when the underlying graph is unweighted and sparse. When restricting to concrete classes of graphs and assuming SETH, planar graphs and minor-free graphs admit truly subquadratic algorithms, while geometric intersection graphs of unit balls, congruent equilateral triangles, and unit segments do not. Unit-disk graphs is one of the major open cases where the complexity of diameter computation remains unknown. More generally, it is conjectured that a truly subquadratic time algorithm exists for pseudo-disk graphs where each pair of objects has at most two intersections on the boundary. In this paper, we show a truly-subquadratic algorithm of running time O^~(n^{2-1/18}), for finding the diameter in a unit-disk graph, whose output differs from the optimal solution by at most 2. This is the first algorithm that provides an additive guarantee in distortion, independent of the size or the diameter of the graph. Our algorithm requires two important technical elements. First, we show that for the intersection graph of pseudo-disks, the graph VC-dimension - either of k-hop balls or the distance encoding vectors - is 4. This contrasts to the VC dimension of the pseudo-disks themselves as geometric ranges (which is known to be 3). Second, we introduce a clique-based r-clustering for geometric intersection graphs, which is an analog of the r-division construction for planar graphs. We also showcase the new techniques by establishing new results for distance oracles for unit-disk graphs with subquadratic storage and O(1) query time. The results naturally extend to unit L₁ or L_∞-disks and fat pseudo-disks of similar size. Last, if the pseudo-disks additionally have bounded ply, we have a truly subquadratic algorithm to find the exact diameter.

A $(1+\varepsilon)\textit{-stretch tree cover}$ of a metric space is a collection of trees, where every pair of points has a $(1+\varepsilon)$-stretch path in one of the trees. The celebrated $\textit{Dumbbell Theorem}$ [Arya et~al. STOC'95] states that any set of $n$ points in $d$-dimensional Euclidean space admits a $(1+\varepsilon)$-stretch tree cover with $O_d(\varepsilon^{-d} \cdot \log(1/\varepsilon))$ trees, where the $O_d$ notation suppresses terms that depend solely on the dimension~$d$. The running time of their construction is $O_d(n \log n \cdot \frac{\log(1/\varepsilon)}{\varepsilon^{d}} + n \cdot \varepsilon^{-2d})$. Since the same point may occur in multiple levels of the tree, the $\textit{maximum degree}$ of a point in the tree cover may be as large as $Ω(\log Φ)$, where $Φ$ is the aspect ratio of the input point set. In this work we present a $(1+\varepsilon)$-stretch tree cover with $O_d(\varepsilon^{-d+1} \cdot \log(1/\varepsilon))$ trees, which is optimal (up to the $\log(1/\varepsilon)$ factor). Moreover, the maximum degree of points in any tree is an $\textit{absolute constant}$ for any $d$. As a direct corollary, we obtain an optimal {routing scheme} in low-dimensional Euclidean spaces. We also present a $(1+\varepsilon)$-stretch $\textit{Steiner}$ tree cover (that may use Steiner points) with $O_d(\varepsilon^{(-d+1)/{2}} \cdot \log(1/\varepsilon))$ trees, which too is optimal. The running time of our two constructions is linear in the number of edges in the respective tree covers, ignoring an additive $O_d(n \log n)$ term; this improves over the running time underlying the Dumbbell Theorem.

The notion of shortcut partition, introduced recently by Chang, Conroy, Le, Milenković, Solomon, and Than [CCL+23], is a new type of graph partition into low-diameter clusters. Roughly speaking, the shortcut partition guarantees that for every two vertices u and v in the graph, there exists a path between u and v that intersects only a few clusters. They proved that any planar graph admits a shortcut partition and gave several applications, including a construction of tree cover for arbitrary planar graphs with stretch 1 + ɛ and O(1) many trees for any fixed ɛ ∈ (0,1). However, the construction heavily exploits planarity in multiple steps, and is thus inherently limited to planar graphs.

While research on the geometry of planar graphs has been active in the past decades, many properties of planar metrics remain mysterious. This paper studies a fundamental aspect of the planar graph geometry: covering planar metrics by a small collection of simpler metrics. Specifically, a tree cover of a metric space $(X, \delta)$ is a collection of trees, so that every pair of points u and v in X has a low-distortion path in at least one of the trees.The celebrated “Dumbbell Theorem” [ADM+95] states that any low-dimensional Euclidean space admits a tree cover with $O(1)$ trees and distortion $1+\varepsilon$, for any fixed $\varepsilon \in(0,1)$. This result has found numerous algorithmic applications, and has been generalized to the wider family of doubling metrics [BFN19]. Does the same result hold for planar metrics? A positive answer would add another evidence to the well-observed connection between Euclidean/doubling metrics and planar metrics.In this work, we answer this fundamental question affirmatively. Specifically, we show that for any given fixed $\varepsilon \in(0,1)$, any planar metric can be covered by $O(1)$ trees with distortion $1+\varepsilon$. Our result for planar metrics follows from a rather general framework: First we reduce the problem to constructing tree covers with additive distortion. Then we introduce the notion of shortcut partition, and draw connection between shortcut partition and additive tree cover. Finally we prove the existence of shortcut partition for any planar metric, using new insights regarding the grid-like structure of planar graphs. To demonstrate the power of our framework:•We establish additional tree cover results beyond planar metrics; in particular, we present an $O(1)$-size tree cover with distortion $1+\varepsilon$ for bounded treewidth metrics;•We obtain several algorithmic applications in planar graphs from our tree cover. The grid-like structure is a technical contribution that we believe is of independent interest. We showcase its applicability beyond tree cover by constructing a simpler and better embedding of planar graphs into $O(1)$-treewidth graphs with small additive distortion, resolving an open problem in this line of research.

Any generic planar closed curve with n crossings can be turned into a simple closed curve by applying O(n3/2) homotopy moves without ever increasing the number of self-crossings; this improves over the O(n2) upper bound from Steinitz [Ency. Math. Wiss. III 1916], and matches the best lower bound. We prove the existence of a positive move that decreases the depth-sum potential at every step. Using similar techniques, we show that any 2-terminal plane graph with n vertices can be reduced to a single edge between the terminals using O(n3/2) electrical transformations, consisting of degree-1 reductions, series-parallel reductions, and ΔY-transformations; this proves a conjecture of Feo and Provan that was open for more than 30 years.

Given two point sets A and B in ℝd of size n each, for some constant dimension d≥ 1, and a parameter ε>0, we present a deterministic algorithm that computes, in n·(ε−1 logn)O(d) time, a perfect matching between A and B whose cost is within a (1+ε) factor of the optimal matching under any ℓp-norm. Although a Monte-Carlo algorithm with a similar running time is proposed by Raghvendra and Agarwal [J. ACM 2020], the best-known deterministic ε-approximation algorithm takes Ω(n3/2) time. Our algorithm constructs a (refinement of a) tree cover of ℝd, and we develop several new tools to apply a tree-cover based approach to compute an ε-approximate perfect matching.

We study vertex sparsification for distances, in the setting of planar graphs with distortion: Given a planar graph G (with edge weights) and a subset of k terminal vertices, the goal is to construct an ε-emulator, which is a small planar graph G′ that contains the terminals and preserves the distances between the terminals up to factor 1+ε.

We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static versions have been extensively studied in the past, surprisingly little is known about dynamic geometric set cover and hitting set. For instance, even for the most basic case of one-dimensional interval set cover and hitting set, no nontrivial results were known. The main contribution of our article are two frameworks that lead to efficient data structures for dynamically maintaining set covers and hitting sets in ℝ 1 and ℝ 2 . The first framework uses bootstrapping and gives a (1 + ε)-approximate data structure for dynamic interval set cover in ℝ 1 with O ( n α / ε) amortized update time for any constant α > 0; in ℝ 2 , this method gives O (1)-approximate data structures for unit-square set cover and hitting set with O ( n 1/2+α ) amortized update time. The second framework uses local modification and leads to a (1 + ε)-approximate data structure for dynamic interval hitting set in ℝ 1 with Õ(1/ε) amortized update time; in ℝ 2 , it gives O (1)-approximate data structures for unit-square set cover and hitting set in the partially dynamic settings with Õ(1) amortized update time.

We prove the first polynomial bound on the number of monotonic homotopy moves required to tighten a collection of closed curves on any compact orientable surface, where the number of crossings in the curve is not allowed to increase at any time during the process. The best known upper bound before was exponential, which can be obtained by combining the algorithm of De Graaf and Schrijver [ J. Comb. Theory Ser. B , 1997] together with an exponential upper bound on the number of possible surface maps. To obtain the new upper bound, we apply tools from hyperbolic geometry, as well as operations in graph drawing algorithms—the cluster and pipe expansions—to the study of curves on surfaces. As corollaries, we present two efficient algorithms for curves and graphs on surfaces. First, we provide a polynomial-time algorithm to convert any given multicurve on a surface into minimal position. Such an algorithm only existed for single closed curves, and it is known that previous techniques do not generalize to the multicurve case. Second, we provide a polynomial-time algorithm to reduce any k -terminal plane graph (and more generally, surface graph) using degree-1 reductions, series-parallel reductions, and Δ Y -transformations for arbitrary integer k . Previous algorithms only existed in the planar setting when k ≤ 4, and all of them rely on extensive case-by-case analysis based on different values of k . Our algorithm makes use of the connection between electrical transformations and homotopy moves and thus solves the problem in a unified fashion.

We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static versions have been extensively studied in the past, surprisingly little is known about dynamic geometric set cover and hitting set. For instance, even for the most basic case of one-dimensional interval set cover and hitting set, no nontrivial results were known. The main contribution of our paper are two frameworks that lead to efficient data structures for dynamically maintaining set covers and hitting sets in $\mathbb{R}^1$ and $\mathbb{R}^2$. The first framework uses bootstrapping and gives a $(1+\varepsilon)$-approximate data structure for dynamic interval set cover in $\mathbb{R}^1$ with $O(n^α/\varepsilon)$ amortized update time for any constant $α> 0$; in $\mathbb{R}^2$, this method gives $O(1)$-approximate data structures for unit-square (and quadrant) set cover and hitting set with $O(n^{1/2+α})$ amortized update time. The second framework uses local modification, and leads to a $(1+\varepsilon)$-approximate data structure for dynamic interval hitting set in $\mathbb{R}^1$ with $\widetilde{O}(1/\varepsilon)$ amortized update time; in $\mathbb{R}^2$, it gives $O(1)$-approximate data structures for unit-square (and quadrant) set cover and hitting set in the \textit{partially} dynamic settings with $\widetilde{O}(1)$ amortized update time.

We prove the first polynomial bound on the number of monotonic homotopy moves required to tighten a collection of closed curves on any compact orientable surface, where the number of crossings in the curve is not allowed to increase at any time during the process. The best known upper bound before was exponential, which can be obtained by combining the algorithm of de Graaf and Schrijver [J. Comb. Theory Ser. B, 1997] together with an exponential upper bound on the number of possible surface maps. To obtain the new upper bound we apply tools from hyperbolic geometry, as well as operations in graph drawing algorithms—the cluster and pipe expansions—to the study of curves on surfaces. As corollaries, we present two efficient algorithms for curves and graphs on surfaces. First, we provide a polynomial-time algorithm to convert any given multicurve on a surface into minimal position. Such an algorithm only existed for single closed curves, and it is known that previous techniques do not generalize to the multicurve case. Second, we provide a polynomial-time algorithm to reduce any k-terminal plane graph (and more generally, surface graph) using degree-1 reductions, series-parallel reductions, and ΔY-transformations for arbitrary integer k. Previous algorithms only existed in the planar setting when k ≤ 4, and all of them rely on extensive case-by-case analysis based on different values of k. Our algorithm makes use of the connection between electrical transformations and homotopy moves, and thus solves the problem in a unified fashion.

Let $A$ and $B$ be two point sets in the plane of sizes $r$ and $n$ respectively (assume $r \leq n$), and let $k$ be a parameter. A matching between $A$ and $B$ is a family of pairs in $A \times B$ so that any point of $A \cup B$ appears in at most one pair. Given two positive integers $p$ and $q$, we define the cost of matching $M$ to be $c(M) = \sum_{(a, b) \in M}\|{a-b}\|_p^q$ where $\|{\cdot}\|_p$ is the $L_p$-norm. The geometric partial matching problem asks to find the minimum-cost size-$k$ matching between $A$ and $B$. We present efficient algorithms for geometric partial matching problem that work for any powers of $L_p$-norm matching objective: An exact algorithm that runs in $O((n + k^2) {\mathop{\mathrm{polylog}}} n)$ time, and a $(1 + \varepsilon)$-approximation algorithm that runs in $O((n + k\sqrt{k}) {\mathop{\mathrm{polylog}}} n \cdot \log\varepsilon^{-1})$ time. Both algorithms are based on the primal-dual flow augmentation scheme; the main improvements involve using dynamic data structures to achieve efficient flow augmentations. With similar techniques, we give an exact algorithm for the planar transportation problem running in $O(\min\{n^2, rn^{3/2}\} {\mathop{\mathrm{polylog}}} n)$ time.

We strengthen the connections between electrical transformations and homotopy from the planar setting - observed and studied since Steinitz - to arbitrary surfaces with punctures. As a result, we improve our earlier lower bound on the number of electrical transformations required to reduce an n-vertex graph on surface in the worst case [SOCG 2016] in two different directions. Our previous Omega(n^{3/2}) lower bound applies only to facial electrical transformations on plane graphs with no terminals. First we provide a stronger Omega(n^2) lower bound when the planar graph has two or more terminals, which follows from a quadratic lower bound on the number of homotopy moves in the annulus. Our second result extends our earlier Omega(n^{3/2}) lower bound to the wider class of planar electrical transformations, which preserve the planarity of the graph but may delete cycles that are not faces of the given embedding. This new lower bound follow from the observation that the defect of the medial graph of a planar graph is the same for all its planar embeddings.

The spectra of signed matrices have played a fundamental role in social sciences, graph theory, and control theory. In this work, we investigate the computational problems of finding symmetric signings of matrices with natural spectral properties. Our results are the following: 1) We characterize matrices that have an invertible signing: a symmetric matrix has an invertible symmetric signing if and only if the support graph of the matrix contains a perfect 2-matching. Further, we present an efficient algorithm to search for an invertible symmetric signing. 2) We use the above-mentioned characterization to give an algorithm to find a minimum increase in the support of a given symmetric matrix so that it has an invertible symmetric signing. 3) We show NP-completeness of the following problems: verifying whether a given matrix has a symmetric signing that is singular or has bounded eigenvalues. However, we also illustrate that the complexity could differ substantially for input matrices that are adjacency matrices of graphs. We use combinatorial techniques in addition to classic results from matching theory.

Given a graph G and a set of terminals T, a distance emulator of G is another graph H (not necessarily a subgraph of G) containing T, such that all the pairwise distances in G between vertices of T are preserved in H. An important open question is to find the smallest possible distance emulator. We prove that, given any subset of k terminals in an n-vertex undirected unweighted planar graph, we can construct in O~(n) time a distance emulator of size O~(min(k^2,sqrt{k * n})). This is optimal up to logarithmic factors. The existence of such distance emulator provides a straightforward framework to solve distance-related problems on planar graphs: Replace the input graph with the distance emulator, and apply whatever algorithm available to the resulting emulator. In particular, our result implies that, on any unweighted undirected planar graph, one can compute all-pairs shortest path distances among k terminals in O~(n) time when k=O(n^{1/3}).

We prove new upper and lower bounds on the number of homotopy moves required to tighten a closed curve on a compact orientable surface (with or without boundary) as much as possible. First, we prove that Ω(n2) moves are required in the worst case to tighten a contractible closed curve on a surface with non-positive Euler characteristic, where n is the number of self-intersection points. Results of Hass and Scott imply a matching O(n2) upper bound for contractible curves on orientable surfaces. Second, we prove that any closed curve on any orientable surface can be tightened as much as possible using at most O(n4) homotopy moves. Except for a few special cases, only naïve exponential upper bounds were previously known for this problem.

Any generic closed curve in the plane can be transformed into a simple closed curve by a finite sequence of local transformations called homotopy moves. We prove that simplifying a planar closed curve with n self-crossings requires Theta(n^{3/2}) homotopy moves in the worst case. Our algorithm improves the best previous upper bound O(n^2), which is already implicit in the classical work of Steinitz; the matching lower bound follows from the construction of closed curves with large defect, a topological invariant of generic closed curves introduced by Aicardi and Arnold. This lower bound also implies that Omega(n^{3/2}) degree-1 reductions, series-parallel reductions, and Delta-Y transformations are required to reduce any planar graph with treewidth Omega(sqrt{n}) to a single edge, matching known upper bounds for rectangular and cylindrical grid graphs. Finally, we prove that Omega(n^2) homotopy moves are required in the worst case to transform one non-contractible closed curve on the torus to another; this lower bound is tight if the curve is homotopic to a simple closed curve.

We present an extension of Voronoi diagrams where not only the distance to the site is taken into account when considering which site the client is going to use, but additional attributes (i.e., prices or weights) are also considered. A cell in this diagram is then the loci of all clients that consider the same set of sites to be relevant. In particular, the precise site a client might use from this candidate set depends on parameters that might change between usages, and the candidate set lists all of the relevant sites. The resulting diagram is significantly more expressive than Voronoi diagrams, but naturally has the drawback that its complexity, even in the plane, might be quite high. Nevertheless, we show that if the attributes of the sites are drawn from the same distribution (note that the locations are fixed), then the expected complexity of the candidate diagram is near linear. To this end, we derive several new technical results, which are of independent interest.

A closed curve in the plane is weakly simple if it is the limit (in the Fréchet metric) of a sequence of simple closed curves. We describe an algorithm to determine whether a closed walk of length n in a simple plane graph is weakly simple in O(n log n) time, improving an earlier O(n3)-time algorithm of Cortese et al. [Discrete Math. 2009]. As an immediate corollary, we obtain the first efficient algorithm to determine whether an arbitrary n-vertex polygon is weakly simple; our algorithm runs in O(n2 log n) time. We also describe algorithms that detect weak simplicity in O(n log n) time for two interesting classes of polygons. Finally, we discuss subtle errors in several previously published definitions of weak simplicity.

The girth of a graph is the minimum weight of all simple cycles of the graph. We study the problem of determining the girth of an $n$-node unweighted undirected planar graph. The first nontrivial algorithm for the problem, given by Djidjev, runs in $O(n^{5/4}\log n)$ time. Chalermsook, Fakcharoenphol, and Nanongkai reduced the running time to $O(n\log^2 n)$. Weimann and Yuster further reduced the running time to $O(n\log n)$. In this paper, we solve the problem in $O(n)$ time.

We study the problem of determining whether an n-node m-edge graph has an even hole, i.e., an induced simple cycle consisting of an even number of nodes. Conforti, Cornuéjols, Kapoor, and Vušković gave the first polynomial-time algorithm for the problem, which runs in O(n40) time. Later, Chudnovsky, Kawarabayashi, and Seymour reduced the running time to O(n31). The best previously known algorithm for the problem, due to da Silva and Vušković, runs in O(n19) time. In this paper, we solve the problem in time O(n11).