We provide a new linear-time algorithm for determining the vertex-connectivity of graphs with bounded genus. This generalizes and streamlines a linear-time algorithm for graphs with bounded crossing number which was recently obtained by Biedl, Bose and Murali [ESA 2024]. Compared to applying the even more recent fixed parameter linear-time algorithm for deciding bounded vertex-connectivity announced by Korhonen [STOC 2025] to graphs of bounded genus,our algorithm is far simpler, its correctness easier to establish, and it makes use of geometric ideas, as is natural for surface-embedded graphs.

An important thread in the study of data-stream algorithms focuses on settings where stream items are active only for a limited time. We introduce a new expiration model, where each item arrives with its own arbitrary expiration time. The special case where items expire in the order that they arrive, which we call consistent expirations, contains the classical sliding-window model of Datar, Gionis, Indyk, and Motwani [SICOMP 2002] and its timestamp-based variant of Braverman and Ostrovsky [FOCS 2007]. Our first set of results explores the expiration streaming model and presents algorithms for several fundamental problems, including approximate counting, uniform sampling, and weighted sampling by efficiently tracking active items without explicitly storing them all. Naturally, these algorithms have many immediate applications, e.g., to range counting. Our second and main set of results for the expiration model designs algorithms for the diameter and k-center problems, where items are points in a metric space. Our results significantly extend those known for the special case of sliding-window streams by Cohen-Addad, Schwiegelshohn, and Sohler [ICALP 2016], and obtain a strictly better approximation factor for the diameter in the important special case of high-dimensional Euclidean metrics. We develop new decomposition and coordination techniques along with a geometric dominance framework to filter out redundant points based on both temporal and spatial proximity.

We investigate algorithms with predictions in computational geometry, specifically focusing on the basic problem of computing 2D Delaunay triangulations. Given a set P of n points in the plane and a triangulation G that serves as a "prediction" of the Delaunay triangulation, we would like to use G to compute the correct Delaunay triangulation DT(P) more quickly when G is "close" to DT(P). We obtain a variety of results of this type, under different deterministic and probabilistic settings, including the following: 1) Define D to be the number of edges in G that are not in DT(P). We present a deterministic algorithm to compute DT(P) from G in O(n + Dlog³ n) time, and a randomized algorithm in O(n+Dlog n) expected time, the latter of which is optimal in terms of D. 2) Let R be a random subset of the edges of DT(P), where each edge is chosen independently with probability ρ. Suppose G is any triangulation of P that contains R. We present an algorithm to compute DT(P) from G in O(nlog log n + nlog(1/ρ)) time with high probability. 3) Define d_{vio} to be the maximum number of points of P strictly inside the circumcircle of a triangle in G (the number is 0 if G is equal to DT(P)). We present a deterministic algorithm to compute DT(P) from G in O(nlog^*n + nlog d_{vio}) time. We also obtain results in similar settings for related problems such as 2D Euclidean minimum spanning trees, and hope that our work will open up a fruitful line of future research.

In this article, we consider the problems of finding in d + 1 dimensions a minimum-volume axis-parallel box, a minimum-volume arbitrarily-oriented box and a minimum-volume convex body into which a given set of d -dimensional unit-radius balls can be packed under translations. The computational problem is neither known to be NP-hard nor to be in NP. We give a constant-factor approximation algorithm for each of these containers based on a reduction to finding a shortest Hamiltonian path in a weighted graph, which in turn models the problem of stabbing the centers of the input balls while keeping them disjoint. We also show that for n such balls, a container of volume O ( n d − 1 d ) is always sufficient and sometimes necessary. As a byproduct, this implies that for d ⩾ 2 there is no finite size ( d + 1 ) -dimensional convex body into which all d -dimensional unit-radius balls can be packed simultaneously.

In the longest plane spanning tree problem, we are given a finite planar point set \(\mathcal{P}\) , and our task is to find a plane (i.e., noncrossing) spanning tree for \(\mathcal{P}\) with maximum total Euclidean edge length. Despite more than two decades of research, it remains open whether this problem is NP-hard. Thus, previous results have focused on polynomial-time algorithms that produce plane trees whose total edge length approximates \(\mathrm{OPT}\) , the maximum possible length. The approximate trees in these algorithms all have small unweighted diameter, typically two to four. It is natural to ask whether this is a common feature of longest plane spanning trees, or an artifact of the specific approximation algorithms. We provide three results to elucidate the interplay between the approximation guarantee and the unweighted diameter of the approximate trees. First, we describe a polynomial-time algorithm to construct a plane tree with diameter at most four and total edge length at least \(0.546\cdot\mathrm{OPT}\) . This constitutes a substantial improvement over the state of the art. Second, we show that a longest plane tree among those with diameter at most three can be found in polynomial time. Third, for any candidate diameter \(d\geq 3\) , we provide upper bounds on the approximation factor that can be achieved by a longest plane tree with diameter at most \( d \) (compared to a longest plane tree without constraints).

We study the heterogeneous facility location game model of n selfish agents on a line, where each agent’s reachable range is a closed subinterval of the line. From two possible facilities, f1 and f2, exactly one is chosen to be built on some point of the line, and the agents have their own preferences p1, p2∈[0,1], p1+p2=1, over these two facilities. The utility of the agent is pi if the placement of the chosen facility fi is inside her reachable range, and zero otherwise. The task is to design mechanisms which get the input from the agents and select the type and placement point of the facility to be built, such that it maximizes the social welfare (defined as the total utility of all agents) while ensuring truthfulness, i.e., incentivizing agents to report their preferences (both facility type and placement) honestly as a dominant strategy. We analyze various scenarios with different setting of privacy of agents’ positional and preference information. When the information is private to the agent, they have the option to misreport it, and hence, we will distinguish between reported information and public information. Initially, we consider the case where all facility preferences are 0 or 1 and we design an optimal mechanism for this case. We then study the case with fractional facility preferences. For the case of public preferences and reported positions, we obtain a mechanism yielding a 3-approximation of the optimum social welfare, and we prove that no deterministic mechanism can achieve approximation ratio better than 4/3. Next, we study the case with public positions and reported preferences. In this setting we design a randomized 2-approximation, obtain lower bounds 3 and 3/2 for the approximation factor of deterministic and randomized strategyproof mechanisms, respectively, and show that a dictator-based approach is a 16/7-approximation mechanism, where the 16/7 factor is tight. Finally, we extend our results to the case of m facilities.

We prove that the single-source shortest-path problem on disk graphs can be solved in $O(n\log n)$ time, and that it can be solved on intersection graphs of fat triangles in $O(n\log^2 n)$ time.

A drawing of a graph is 1-planar if each edge participates in at most one crossing and adjacent edges do not cross. Up to symmetry, each crossing in a 1-planar drawing belongs to one out of six possible crossing types, where a type characterizes the subgraph induced by the four vertices of the crossing edges. Each of the 63 possible nonempty subsets S of crossing types gives a recognition problem: does a given graph admit an S-restricted drawing, that is, a 1-planar drawing where the crossing type of each crossing is in S? We show that there is a set Sbad with three crossing types and the following properties: If S contains no crossing type from Sbad, then the recognition of graphs that admit an S-restricted drawing is fixed-parameter tractable with respect to the treewidth of the input graph. If S contains any crossing type from Sbad, then it is NP-hard to decide whether a graph has an S-restricted drawing, even when considering graphs of constant pathwidth. We also extend this characterization of crossing types to 1-planar straight-line drawings and show the same complexity behaviour parameterized by treewidth.

We consider the following two algorithmic problems: given a graph G and a subgraph H ⊆ G, decide whether H is an isometric or a geodesically convex subgraph of G. It is relatively easy to see that the problems can be solved by computing the distances between all pairs of vertices. We provide a conditional lower bound showing that, for sparse graphs with n vertices and Θ(n) edges, we cannot expect to solve the problem in O(n^{2-ε}) time for any constant ε > 0. We also show that the problem can be solved in subquadratic time for planar graphs and in near-linear time for graphs of bounded treewidth. Finally, we provide a near-linear time algorithm for the setting where G is a plane graph and H is defined by a few cycles in G.

We study the problem of computing the diameter and the mean distance of a continuous graph, i.e., a connected graph where all points along the edges, instead of only the vertices, must be taken into account. It is known that for continuous graphs with m edges these values can be computed in roughly O(m²) time. In this paper, we use geometric techniques to obtain subquadratic time algorithms to compute the diameter and the mean distance of a continuous graph for two well-established classes of sparse graphs. We show that the diameter and the mean distance of a continuous graph of treewidth at most k can be computed in O(n log^O(k) n) time, where n is the number of vertices in the graph. We also show that computing the diameter and mean distance of a continuous planar graph with n vertices and F faces takes O(n F log n) time.

We show that each set of n ⩾ 2 points in the plane in general position has a straight-line matching with at least ( 5 n + 1 ) / 27 edges whose segments form a connected set, and such a matching can be computed in O ( n log ⁡ n ) time. As an upper bound, we show that for some planar point sets in general position the largest matching whose segments form a connected set has ⌈ n − 1 3 ⌉ edges. We also consider a colored version, where each edge of the matching should connect points with different colors.

A terrain is an $x$-monotone polygon whose lower boundary is a single line segment. We present an algorithm to find in a terrain a triangle of largest area in $O(nlog n)$ time, where $n$ is the number of vertices defining the terrain. The best previous algorithm for this problem has a running time of $O(n^2)$.

Let $P$ be a set of at most $n$ points and let $R$ be a set of at most $n$ geometric ranges, such as for example disks or rectangles, where each $p \in P$ has an associated supply $s_{p} > 0$, and each $r \in R$ has an associated demand $d_{r} > 0$. A (many-to-many) matching is a set $\mathcal{A}$ of ordered triples $(p,r,a_{pr}) \in P \times R \times \mathbb{R}_{>0}$ such that $p \in r$ and the $a_{pr}$'s satisfy the constraints given by the supplies and demands. We show how to compute a maximum matching, that is, a matching maximizing $\sum_{(p,r,a_{pr}) \in \mathcal{A}} a_{pr}$. Using our techniques, we can also solve minimum bottleneck problems, such as computing a perfect matching between a set of $n$ red points $P$ and a set of $n$ blue points $Q$ that minimizes the length of the longest edge. For the $L_\infty$-metric, we can do this in time $O(n^{1+\varepsilon})$ in any fixed dimension, for the $L_2$-metric in the plane in time $O(n^{4/3 + \varepsilon})$, for any $\varepsilon > 0$.

Abstract We study the problem of searching for a target at some unknown location in $$\mathbb {R}^d$$ R d when additional information regarding the position of the target is available in the form of predictions. In our setting, predictions come as approximate distances to the target: for each point $$p\in \mathbb {R}^d$$ p ∈ R d that the searcher visits, we obtain a value $$\lambda (p)$$ λ ( p ) such that $$|p\varvec{t}|\le \lambda (p) \le c\cdot |p\varvec{t}|$$ | p t | ≤ λ ( p ) ≤ c · | p t | , where $$c\ge 1$$ c ≥ 1 is a fixed constant, $$\varvec{t}$$ t is the position of the target, and $$|p\varvec{t}|$$ | p t | is the Euclidean distance of p to $$\varvec{t}$$ t . The cost of the search is the length of the path followed by the searcher. Our main positive result is a strategy that achieves $$O(c^d)$$ O ( c d ) -competitive ratio, even when the constant c is unknown. We also give a lower bound of roughly $$(c/4)^{d-1}$$ ( c / 4 ) d - 1 on the competitive ratio of any search strategy in $$\mathbb R^d$$ R d , assuming that $$c\ge 4$$ c ≥ 4 .

Abstract For a set $${\mathcal {Q}}$$ Q of points in the plane and a real number $$\delta \ge 0$$ δ ≥ 0 , let $${\mathbb {G}}_\delta ({\mathcal {Q}})$$ G δ ( Q ) be the graph defined on $${\mathcal {Q}}$$ Q by connecting each pair of points at distance at most $$\delta $$ δ .We consider the connectivity of $${\mathbb {G}}_\delta ({\mathcal {Q}})$$ G δ ( Q ) in the best scenario when the location of a few of the points is uncertain, but we know for each uncertain point a line segment that contains it. More precisely, we consider the following optimization problem: given a set $${\mathcal {P}}$$ P of $$n-k$$ n - k points in the plane and a set $${\mathcal {S}}$$ S of k line segments in the plane, find the minimum $$\delta \ge 0$$ δ ≥ 0 with the property that we can select one point $$p_s\in s$$ p s ∈ s for each segment $$s\in {\mathcal {S}}$$ s ∈ S and the corresponding graph $${\mathbb {G}}_\delta ( {\mathcal {P}}\cup \{ p_s\mid s\in {\mathcal {S}}\})$$ G δ ( P ∪ { p s ∣ s ∈ S } ) is connected. It is known that the problem is NP-hard. We provide an algorithm to exactly compute an optimal solution in $${{\,\mathrm{{\mathcal {O}}}\,}}(f(k) n \log n)$$ O ( f ( k ) n log n ) time, for a computable function $$f(\cdot )$$ f ( · ) . This implies that the problem is FPT when parameterized by k. The best previous algorithm uses $${{\,\mathrm{{\mathcal {O}}}\,}}((k!)^k k^{k+1}\cdot n^{2k})$$ O ( ( k ! ) k k k + 1 · n 2 k ) time and computes the solution up to fixed precision.

We study the problem of $k$-means clustering in the space of straight-line segments in $\mathbb{R}^{2}$ under the Hausdorff distance. For this problem, we give a $(1+ε)$-approximation algorithm that, for an input of $n$ segments, for any fixed $k$, and with constant success probability, runs in time $O(n+ ε^{-O(k)} + ε^{-O(k)}\cdot \log^{O(k)} (ε^{-1}))$. The algorithm has two main ingredients. Firstly, we express the $k$-means objective in our metric space as a sum of algebraic functions and use the optimization technique of Vigneron~\cite{Vigneron14} to approximate its minimum. Secondly, we reduce the input size by computing a small size coreset using the sensitivity-based sampling framework by Feldman and Langberg~\cite{Feldman11, Feldman2020}. Our results can be extended to polylines of constant complexity with a running time of $O(n+ ε^{-O(k)})$.

Let $G$ be an intersection graph of $n$ geometric objects in the plane. We show that a maximum matching in $G$ can be found in $O(\rho^{3\omega/2}n^{\omega/2})$ time with high probability, where $\rho$ is the density of the geometric objects and $\omega>2$ is a constant such that $n \times n$ matrices can be multiplied in $O(n^\omega)$ time. The same result holds for any subgraph of $G$, as long as a geometric representation is at hand. For this, we combine algebraic methods, namely computing the rank of a matrix via Gaussian elimination, with the fact that geometric intersection graphs have small separators. We also show that in many interesting cases, the maximum matching problem in a general geometric intersection graph can be reduced to the case of bounded density. In particular, a maximum matching in the intersection graph of any family of translates of a convex object in the plane can be found in $O(n^{\omega/2})$ time with high probability, and a maximum matching in the intersection graph of a family of planar disks with radii in $[1, \Psi]$ can be found in $O(\Psi^6\log^{11} n + \Psi^{12 \omega} n^{\omega/2})$ time with high probability.

Abstract We consider the problem of computing the distance-based representative skyline in the plane, a problem introduced by Tao, Ding, Lin and Pei [Proc. 25th IEEE International Conference on Data Engineering (ICDE), 2009] and independently considered by Dupin, Nielsen and Talbi [Mathematics; Optimization and Learning - Third International Conference, OLA 2020] in the context of multi-objective optimization. Given a set P of n points in the plane and a parameter k, the task is to select k points of the skyline defined by P (also known as Pareto front for P) to minimize the maximum distance from the points of the skyline to the selected points. We show that the problem can be solved in $$O(n\log h)$$ O ( n log h ) time, where h is the number of points in the skyline of P. We also show that the decision problem can be solved in $$O(n\log k)$$ O ( n log k ) time and the optimization problem can be solved in $$O(n \log k + n {{\,\textrm{loglog}\,}}n)$$ O ( n log k + n loglog n ) time. This improves previous algorithms and is optimal for a large range of values of k.

We consider the problem of computing Shapley values for points in the plane, where each point is interpreted as a player, and the value of a coalition is defined by the area or the perimeter of usual geometric objects, such as the convex hull or the minimum axis-parallel bounding box. For sets of n points in the plane, we show how to compute in roughly $$O(n^{3/2})$$ time the Shapley values for the area of the minimum axis-parallel bounding box and the area of the union of the rectangles spanned by the origin and the input points. When the points form an increasing or decreasing chain, the running time can be improved to near-linear. In all these cases, we use linearity of the Shapley values and algebraic methods. We also show that Shapley values for the area and the perimeter of the convex hull can be computed in $$O(n^2)$$ time, while for the minimum enclosing disk it takes $$O(n^3)$$ time. These problems are closely related to the model of stochastic point sets considered in computational geometry, but here we have to consider random insertion orders of the points instead of a probabilistic existence of points.

The inverse geodesic length of a graph G is the sum of the inverse of the distances between all pairs of distinct vertices of G . In some domains, it is known as the Harary index or the global efficiency of the graph. We show that, if G is planar and has n vertices, then the inverse geodesic length of G can be computed in roughly O ( n 9/5 ) time. We also show that, if G has n vertices and treewidth at most k , then the inverse geodesic length of G can be computed in O ( n log O ( k ) n ) time. In both cases, we use techniques developed for computing the sum of the distances, which does not have “inverse” component, together with batched evaluations of rational functions.

Let D be a set of n disks in the plane. The disk graph G D for D is the undirected graph with vertex set D in which two disks are joined by an edge if and only if they intersect. The directed transmission graph G D → for D is the directed graph with vertex set D in which there is an edge from a disk D 1 ∈ D to a disk D 2 ∈ D if and only if D 1 contains the center of D 2 . Given D and two non-intersecting disks s , t ∈ D , we show that a minimum s - t vertex cut in G D or in G D → can be found in O ( n 3 / 2 polylog n ) expected time. To obtain our result, we combine an algorithm for the maximum flow problem in general graphs with dynamic geometric data structures to manipulate the disks. As an application, we consider the barrier resilience problem in a rectangular domain. In this problem, we have a vertical strip S bounded by two vertical lines, L ℓ and L r , and a collection D of disks. Let a be a point in S above all disks of D , and let b a point in S below all disks of D . The task is to find a curve from a to b that lies in S and that intersects as few disks of D as possible. Using our improved algorithm for minimum cuts in disk graphs, we can solve the barrier resilience problem in O ( n 3 / 2 polylog n ) expected time.

In this paper we shall encounter three open problems in Computational Geometry that are, in my opinion, interesting for a general audience interested in algorithms.

Abstract We introduce a problem called minimum shared‐power edge cut (MSPEC). The input to the problem is an undirected edge‐weighted graph with distinguished vertices s and t, and the goal is to find an s‐t cut by assigning “powers” at the vertices and removing an edge if the sum of the powers at its endpoints is at least its weight. The objective is to minimize the sum of the assigned powers. MSPEC is a graph generalization of a barrier coverage problem in a wireless sensor network: given a set of unit disks with centers in a rectangle, what is the minimum total amount by which we must shrink the disks to permit an intruder to cross the rectangle undetected, that is, without entering any disk. This is a more sophisticated measure of barrier coverage than the minimum number of disks whose removal breaks the barrier. We develop a fully polynomial time approximation scheme for MSPEC. We give polynomial time algorithms for the special cases where the edge weights are uniform, or the power values are restricted to a bounded set. Although MSPEC is related to network flow and matching problems, its computational complexity (in P or NP‐hard) remains open.

We consider the problem of finding a subcomplex $\mathcal{K}'$ of a simplicial complex $\mathcal{K}$ such that $\mathcal{K}'$ is homeomorphic to the 2-dimensional sphere, $\mathbb{S}^2$. We study two variants of this problem. The first asks if there exists such a $\mathcal{K}'$ with at most $\mathcal{K}$ triangles, and we show that this variant is ${\mathsf{W[1]}}$-hard and, assuming the exponential time hypothesis, admits no $n^{o(\sqrt{k})}$-time algorithm. We also give an algorithm that is tight with regard to this lower bound. The second problem is the dual of the first and asks if $\mathcal{K}'$ can be found by removing at most $k$ triangles from $\mathcal{K}$. This variant has an immediate $\mathcal{O}(3^{k}poly(|\mathcal{K}|))$-time algorithm, and we show that it admits a polynomial kernelization to $\mathcal{O}(k^2)$ triangles, as well as a polynomial compression to a weighted version with bit-size $\mathcal{O}(k \log k)$. This article has been changed.

In this article, we show how to compute for n -vertex planar graphs in O ( n 11/6 polylog( n )) expected time the diameter and the sum of the pairwise distances. The algorithms work for directed graphs with real weights and no negative cycles. In O ( n 15/8 polylog( n )) expected time, we can also compute the number of pairs of vertices at distances smaller than a given threshold. These are the first algorithms for these problems using time O ( n c ) for some constant c < 2, even when restricted to undirected, unweighted planar graphs.

We prove a generalization of Pál's 1921 conjecture that if a convex shape P can be placed in any orientation inside a convex shape Q in the plane, then P can also be turned continuously through 360° inside Q. We also prove a lower bound of Omega(m n^{2}) on the number of combinatorially distinct maximal placements of a convex m-gon P in a convex n-gon Q. This matches the upper bound proven by Agarwal et al.

Let $B$ be a set of $n$ axis-parallel boxes in $\mathbb{R}^d$ such that each box has a corner at the origin and the other corner in the positive quadrant of $\mathbb{R}^d$, and let $k$ be a positive integer. We study the problem of selecting $k$ boxes in $B$ that maximize the volume of the union of the selected boxes. This research is motivated by applications in skyline queries for databases and in multicriteria optimization, where the problem is known as the hypervolume subset selection problem. It is known that the problem can be solved in polynomial time in the plane, while the best known running time in any dimension $d \ge 3$ is $Ω\big(\binom{n}{k}\big)$. We show that: - The problem is NP-hard already in 3 dimensions. - In 3 dimensions, we break the bound $Ω\big(\binom{n}{k}\big)$, by providing an $n^{O(\sqrt{k})}$ algorithm. - For any constant dimension $d$, we present an efficient polynomial-time approximation scheme.

We show how to compute in O(n11/6 polylog(n)) expected time the diameter and the sum of the pairwise distances in an undirected planar graph with n vertices and positive edge weights. These are the first algorithms for these problems using time O(nc) for some constant c < 2.

We consider the problem of finding a subcomplex K' of a simplicial complex K such that K' is homeomorphic to the 2-dimensional sphere, S^2. We study two variants of this problem. The first asks if there exists such a K' with at most k triangles, and we show that this variant is W[1]-hard and, assuming ETH, admits no O(n^{o(sqrt(k))}) time algorithm. We also give an algorithm that is tight with regards to this lower bound. The second problem is the dual of the first, and asks if K' can be found by removing at most k triangles from K. This variant has an immediate O(3^k poly(|K|)) time algorithm, and we show that it admits a polynomial kernelization to O(k^2) triangles, as well as a polynomial compression to a weighted version with bit-size O(k log k).

We consider the following geometric optimization problem: find a convex polygon of maximum area contained in a given simple polygon $P$ with $n$ vertices. We give a randomized near-linear-time $(1-\varepsilon)$-approximation algorithm for this problem: in $O(n( \log^2 n + (1/\varepsilon^3) \log n + 1/\varepsilon^4))$ time we find a convex polygon contained in $P$ that, with probability at least $2/3$, has area at least $(1-\varepsilon)$ times the area of an optimal solution. We also obtain similar results for the variant of computing a convex polygon inside $P$ with maximum perimeter. To achieve these results we provide new results in geometric probability. The first result is a bound relating the area of the largest convex body inside $P$ to the probability that two points chosen uniformly at random inside $P$ are mutually visible. The second result is a bound on the expected value of the difference between the perimeter of any planar convex body $K$ and the perimeter of the convex hull of a uniform random sample inside $K$.

Consider a sequence s_1,...,s_n of points in the plane. We want to find all maximal subsequences with a given hereditary property P: find for all indices i the largest index j^*(i) such that s_i,...,s_{j^*(i)} has property P. We provide a general methodology that leads to the following specific results: - In O(n log^2 n) time we can find all maximal subsequences with diameter at most 1. - In O(n log n loglog n) time we can find all maximal subsequences whose convex hull has area at most 1. - In O(n) time we can find all maximal subsequences that define monotone paths in some (subpath-dependent) direction. The same methodology works for graph planarity, as follows. Consider a sequence of edges e_1,...,e_n over a vertex set V. In O(n log n) time we can find, for all indices i, the largest index j^*(i) such that (V,{e_i,..., e_{j^*(i)}}) is planar.

We consider the following geometric optimization problem: find a convex polygon of maximum area contained in a given simple polygon P with n vertices. We give a randomized near-linear-time (1 − ϵ)-approximation algorithm for this problem: in O((n/ϵ6) log2 n log(1/δ)) time we find a convex polygon contained in P that, with probability at least 1 − δ, has area at least (1 − ϵ) times the area of an optimal solution.

Let $G$ be a graph embedded in an orientable surface $\Sigma$, possibly with edge weights, and denote by ${\rm len}(\gamma)$ the length (the number of edges or the sum of the edge weights) of a cycle $\gamma$ in $G$. The stretch of a graph embedded on a surface is the minimum of ${\rm len}(\alpha)\cdot {\rm len}(\beta)$ over all pairs of cycles $\alpha$ and $\beta$ that cross exactly once. We provide two algorithms to compute the stretch of an embedded graph, each based on a different principle. The first algorithm is based on surgery and computes the stretch in time $O(g^4 n \log n)$ with high probability, or in time $O(g^4 n \log^2 n)$ in the worst case, where $g$ is the genus of the surface $\Sigma$ and $n$ is the number of vertices in $G$. The second algorithm is based on using a short homology basis and computes the stretch in time $O(n^2\log n + n^2g + ng^3)$.

We study the following separation problem: Given n connected curves and two points s and t in the plane, compute the minimum number of curves one needs to retain so that any path connecting s to t intersects some of the retained curves. We give the first polynomial (O(n3)) time algorithm for the problem, assuming that the curves have reasonable computational properties. The algorithm is based on considering the intersection graph of the curves, defining, in this graph, an appropriate family of closed walks that satisfies the 3-path-condition, and arguing that a shortest cycle in the family gives an optimal solution. The 3-path-condition has been used mainly in topological graph theory, and thus its use here reveals the connection to topology. We also show that the generalized version, where several input points are to be separated, is NP-hard for natural families of curves, like segments in two directions or unit circles.

Let $G$ be a directed graph with $n$ vertices and nonnegative weights in its directed edges, embedded on a surface of genus $g$, and let $f$ be an arbitrary face of $G$. We describe a randomized algorithm to preprocess the graph in $O(gn \log n)$ time with high probability, so that the shortest-path distance from any vertex on the boundary of $f$ to any other vertex in $G$ can be retrieved in $O(\log n)$ time. Our result directly generalizes the $O(n\log n)$-time algorithm of Klein [Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005] for multiple-source shortest paths in planar graphs. Intuitively, our preprocessing algorithm maintains a shortest-path tree as its source point moves continuously around the boundary of $f$. As an application of our algorithm, we describe algorithms to compute a shortest noncontractible or nonseparating cycle in embedded, undirected graphs in $O(g^2 n\log n)$ time with high probability. Our high-probability time bounds hold in the worst case for generic edge weights or with an additional $O(\log n)$ factor for arbitrary edge weights.

A graph is near-planar if it can be obtained from a planar graph by adding an edge. We show the surprising fact that it is NP-hard to compute the crossing number of near-planar graphs. A graph is 1-planar if it has a drawing where every edge is crossed by at most one other edge. We show that it is NP-hard to decide whether a given near-planar graph is 1-planar. The main idea in both reductions is to consider the problem of simultaneously drawing two planar graphs inside a disk, with some of its vertices fixed at the boundary of the disk. This leads to the concept of anchored embedding, which is of independent interest. As an interesting consequence we obtain a new, geometric proof of NP-completeness of the crossing number problem, even when restricted to cubic graphs. This resolves a question of Hliněný.

Let G be a graph cellularly embedded on a surface $\mathcal{S}$. We consider the problem of determining whether G contains a cycle (i.e., a closed walk without repeated vertices) of a certain topological type in $\mathcal{S}$. We show that the problem can be answered in linear time when the topological type is one of the following: contractible, noncontractible, or nonseparating. In each case, we obtain the same time complexity if we require the cycle to contain a given vertex. On the other hand, we prove that the problem is NP-complete when considering separating or splitting cycles. We also show that deciding the existence of a separating or a splitting cycle of length at most k is fixed-parameter tractable with respect to k plus the genus of the surface.

We study the parameterized complexity of the k -center problem on a given n -point set P in ℝ d , with the dimension d as the parameter. We show that the rectilinear 3-center problem is fixed-parameter tractable, by giving an algorithm that runs in O ( n log n ) time for any fixed dimension d . On the other hand, we show that this is unlikely to be the case with both the Euclidean and rectilinear k -center problems for any k ≥ 2 and k ≥ 4 respectively. In particular, we prove that deciding whether P can be covered by the union of 2 balls of given radius or by the union of 4 cubes of given side length is W[1]-hard with respect to d , and thus not fixed-parameter tractable unless FPT=W[1]. For the Euclidean case, we also show that even an n o ( d ) -time algorithm does not exist, unless there is a 2 o ( n ) -time algorithm for n -variable 3SAT, that is, the Exponential Time Hypothesis fails.

A graph is near-planar if it can be obtained from a planar graph by adding an edge. We show that it is NP-hard to compute the crossing number of near-planar graphs. The main idea in the reduction is to consider the problem of simultaneously drawing two planar graphs inside a disk, with some of its vertices fixed at the boundary of the disk. This approach can be used to prove hardness of some other geometric problems. As an interesting consequence we obtain a new, geometric proof of NP-completeness of the crossing number problem, even when restricted to cubic graphs. This resolves a question of Hlinený.

Let G be an unweighted graph of complexity n cellularly embedded in a surface (orientable or not) of genus g. We describe improved algorithms to compute (the length of) a shortest non-contractible and a shortest non-separating cycle of G.

Let D be a weighted directed graph cellularly embedded in a surface of genus g, orientable or not, possibly with boundary. We describe algorithms to compute a shortest non-contractible and a shortest surface non-separating cycle in D. This generalizes previous results that only dealt with undirected graphs.

Proportional symbol maps visualize numerical data associated with point locations by placing a scaled symbol—typically an opaque disk or square—at the corresponding point on a map. The area of each symbol is proportional to the numerical value associated with its location. Every visually meaningful proportional symbol map will contain at least some overlapping symbols. These need to be drawn in such a way that the user can still judge their relative sizes accurately. We identify two types of suitable drawings: physically realizable drawings and stacking drawings. For these we study the following two problems: Max-Min—maximize the minimum visible boundary length of each symbol—and Max-Total—maximize the total visible boundary length over all symbols. We show that both problems are NP-hard for physically realizable drawings. Max-Min can be solved in O(n 2log n) time for stacking drawings, which can be improved to O(nlog n) time when the input has certain properties. We also implemented several methods to compute stacking drawings: our solution to the Max-Min problem performs best on the data sets considered.

We consider the problem of finding obnoxious centers in graphs. For arbitrary graphs with n vertices and m edges, we give a randomized algorithm with $O(n\log^{2}n+m\log n)$ expected time. For planar graphs, we give algorithms with $O(n\log n)$ expected time and $O(n\log^{3}n)$ worst-case time. For graphs with bounded treewidth, we give an algorithm taking $O(n\log n)$ worst-case time. The algorithms make use of parametric search and several results for computing distances on graphs of bounded treewidth and planar graphs.

We give a polynomial-time algorithm to find a shortest contractible cycle (i.e., a closed walk without repeated vertices) in a graph embedded in a surface. This answers a question posed by Hutchinson. In contrast, we show that finding a shortest contractible cycle through a given vertex is NP-hard. We also show that finding a shortest separating cycle in an embedded graph is NP-hard. This answers a question posed by Mohar and Thomassen.

A cycle on a combinatorial surface is tight if it as short as possible in its (free) homotopy class. We describe an algorithm to compute a single tight, noncontractible, essentially simple cycle on a given orientable combinatorial surface in O ( n log n ) time. The only method previously known for this problem was to compute the globally shortest noncontractible or nonseparating cycle in O (min{ g 3 , n }, n log n ) time, where g is the genus of the surface. As a consequence, we can compute the shortest cycle freely homotopic to a chosen boundary cycle in O ( n log n ) time, a tight octagonal decomposition in O ( gn log n ) time, and a shortest contractible cycle enclosing a nonempty set of faces in O ( n log 2 n ) time.

We give a polynomial-time algorithm to find a shortest contractible cycle (i.e. a closed walk without repeated vertices) in a graph embedded in a surface. This answers a question posed by Hutchinson. In contrast, we show that finding a shortest contractible cycle through a given vertex is NP-hard. We also show that finding a shortest separating cycle in an embedded graph is NP-hard. This answers a question posed by Mohar and Thomassen.

We study the problem of aligning as many points as possible horizontally, vertically, or diagonally, when each point is allowed to be placed anywhere in its own, given region. Different shapes of placement regions and different sets of alignment orientations are also considered. More generally, we assume that a graph is given on the points, and only the alignments of points that are connected in the graph count. We show that for planar graphs the problem is NP-hard, and we provide inapproximability results for general graphs. For the case of trees and planar graphs, we give approximation algorithms whose performance depends upon the shape of the given regions and the set of orientations. When the orientations to consider are the ones given by the axes and the regions are axis-parallel rectangles, we obtain a polynomial time approximation scheme.

In this paper we present an efficient algorithm to test if two given paths are homotopic; that is, whether they wind around obstacles in the plane in the same way. For simple paths specified by n line segments with obstacles described by n points, our algorithm runs in O(n log n) time, which we show is tight. For self-intersecting paths the problem is related to Hopcroft's problem.

We study the problem of computing schematized versions of network maps , like railroad maps. Every path of the schematized map has two or three links with restricted orientations, and topologically, the schematized map must be equivalent to the input map. Our approach applies to several types of schematizations, and certain additional constraints can be added. In the general case our algorithm takes $O(n\log^3n)$ time, and when all paths in the input are monotone in some (not necessarily the same) direction, it runs in $O(n\log n)$ time.