Arrow Research search

Author name cluster

Csaba D. Tóth

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

26 papers
2 author rows

Possible papers

26

TCS Journal 2026 Journal Article

Erdős-Szekeres Maker-Breaker games

  • Aleksa Džuklevski
  • Dömötör Pálvölgyi
  • Alexey Pokrovskiy
  • Csaba D. Tóth
  • Tomáš Valla
  • Lander Verlinde

We present new results on Maker-Breaker games arising from the Erdős-Szekeres problem in planar geometry. This classical problem asks how large a set in general position has to be to ensure the existence of $n$ points that are the vertices of a convex $n$-gon. Moreover, Erdős further extended this problem by asking what happens if we also require that this $n$-gon has an empty interior. In a 2-player Maker-Breaker setting, this problem inspires two main games. In both games, Maker tries to obtain an empty convex $k$-gon, while Breaker tries to prevent her from doing so. The games differ only in which points can comprise the winning $k$-gons: in the monochromatic version the points of both players can make up a $k$-gon, while in the bichromatic version only Maker's points contribute to such a polygon. Both settings are studied in this paper. We show that in the monochromatic game, Maker always wins. Even in a biased game where Breaker is allowed to place $s$ points per round, for any constant $s \geq 1$, Maker has a winning strategy. In the bichromatic setting, Maker still wins whenever Breaker is allowed to place $s$ points per round for any constant $s<2$. This settles an open problem posed by Aichholzer et al. (2019). Furthermore, we show that there are games that are not a lost cause for Breaker. Whenever $k\ge 8$ and Breaker is allowed to play 12 or more points per round, she has a winning strategy. We also consider the one-round bichromatic game (a. k. a. \ the offline version). In this setting, we show that Breaker wins if she can place twice as many points as Maker but if the bias is less than $2$, then Maker wins for large enough set of points.

Details DOI

TCS Journal 2024 Journal Article

Observation routes and external watchman routes

  • Adrian Dumitrescu
  • Csaba D. Tóth

We introduce the Observation Route Problem (ORP) defined as follows: Given a set of n pairwise disjoint obstacles (regions) in the plane, find a shortest tour (route) such that an observer walking along this tour can see (observe) each obstacle from some point of the tour. The observer does not need to see the entire boundary of an obstacle. The tour is not allowed to intersect the interior of any region (i. e. , the regions are obstacles and therefore out of bounds). The problem exhibits similarity to both the Traveling Salesman Problem with Neighborhoods (TSPN) and the External Watchman Route Problem (EWRP). We distinguish two variants: the range of visibility is either limited to a bounding rectangle, or unlimited. We obtain the following results: (I) Given a family of n disjoint convex bodies in the plane, computing a shortest observation route does not admit a ( c log ⁡ n ) -approximation unless P = NP for an absolute constant c > 0. (This holds for both limited and unlimited vision.) (II) Given a family of disjoint convex bodies in the plane, computing a shortest external watchman route is NP -hard. (This holds for both limited and unlimited vision; and even for families of axis-aligned squares.) (III) Given a family of n disjoint fat convex polygons in the plane, an observation tour whose length is at most O ( log ⁡ n ) times the optimal can be computed in polynomial time. (This holds for limited vision.) (IV) For every n ≥ 5, there exists a convex polygon with n sides and all angles obtuse such that its perimeter is not a shortest external watchman route. This refutes a conjecture by Absar and Whitesides (2006).

Details DOI

FOCS Conference 2024 Conference Paper

Towards Instance-Optimal Euclidean Spanners

  • Hung Le 0001
  • Shay Solomon
  • Cuong Than
  • Csaba D. Tóth
  • Tianyi Zhang 0008

Euclidean spanners are important geometric objects that have been extensively studied since the 1980s. The two most basic “compactness” measures of a Euclidean spanner $E$ 1 2 We shall identify a graph $H = (X, E)$ with its edge set $E$. All edge weights are given by the Euclidean distances. are the size (number of edges) $\vert E\vert$ and the weight (sum of edge weights) $\Vert E\Vert$. The state-of-the-art constructions of Euclidean $(1+\epsilon)$ -spanners in $\mathbb{R}^{d}$ have $o_{d}(_{n\cdot\epsilon^{-d+1}})$ edges (or sparsity $O_{d}(\epsilon^{-d+1}))$ and weight $O_{d}(\epsilon^{-d} \log \epsilon^{-1}) \cdot\Vert E_{\text{mst}}\Vert$ (or lightness $O_{d}(\epsilon^{-d}\log\epsilon^{-1}))$; here $O_{d}$ suppresses a factor of $d^{O(d)}$ and $\Vert E_{\text{mst}}\Vert$ denotes the weight of a minimum spanning tree of the input point set. Importantly, these two upper bounds are (near-)optimal (up to the $d^{O(d)}$ factor and disregarding the factor of $\log(\epsilon^{-1})$ in the lightness bound) for some extremal instances [Le and Solomon, 2019], and therefore they are (near-)optimal in an existential sense. Moreover, both these upper bounds are attained by the same construction-the classic greedy spanner, whose sparsity and lightness are not only existentially optimal, but they also significantly outperform those of any other Euclidean spanner construction studied in an experimental study by [Farshi-Gudmundsson, 2009] for various practical point sets in the plane. This raises the natural question of whether the greedy spanner is (near-) optimal for any point set instance? Motivated by this question, we initiate the study of instance optimal Euclidean spanners. Our results are two-fold. •Rather surprisingly (given the aforementioned experimental study), we demonstrate that the greedy spanner is far from being instance optimal, even when allowing its stretch to grow. More concretely, we design two hard instances of point sets in the plane, where the greedy $(1+x\epsilon)$ -spanner (for basically any parameter $x \geq 1$ ) has $\Omega_{x}(\epsilon^{-1/2})\cdot\vert E_{\text{spa}} \vert$ edges and weight $\Omega_{x}(\epsilon^{-1})\cdot\Vert E_{\text{light}}\Vert$, where $E_{\text{spa}}$ and $E_{\text{light}}$ denote the per-instance sparsest and lightest $(1 +\epsilon)$ -spanners, respectively, and the $\Omega_{x}$ notation suppresses a polynomial dependence on $1/x$. •As our main contribution, we design a new construction of Euclidean spanners, which is inherently different from known constructions, achieving the following bounds: a stretch of $1+\epsilon\cdot 2^{O(\log^{*}(d/\epsilon)}$ with $O(1)\cdot\vert E_{\text{spa}}\vert$ edges and weight $O(1)$. $\Vert E_{ \text{light}}\Vert$. In other words, we show that a slight increase to the stretch suffices for obtaining instance optimality up to an absolute constant for both sparsity and lightness. Remarkably, there is only a log-star dependence on the dimension in the stretch, and there is no dependence on it whatsoever in the number of edges and weight. In general, for any integer $k\geq 1$, we can construct a Euclidean spanner in $\mathbb{R}^{d}$ of stretch $1+\epsilon\cdot 2^{O(k)}$ with $O(\log^{(k)}(\epsilon^{-1})+\log^{(k-1)}(d))\cdot\vert E_{\text{spa}}\vert$ edges and weight $O(\log^{(k)}(\epsilon^{-1})+\log^{(k-1)}(d))\cdot\Vert E_{\text{light}}\Vert$, where $\log^{(k)}$ denotes the k-iterated logarithm.

Details

TCS Journal 2022 Journal Article

Reconfiguration of connected graph partitions via recombination

  • Hugo A. Akitaya
  • Matias Korman
  • Oliver Korten
  • Diane L. Souvaine
  • Csaba D. Tóth

Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph G. A partition of V ( G ) is connected if every part induces a connected subgraph. In many applications, it is desirable to obtain parts of roughly the same size, possibly with some slack s. A Balanced Connected k -Partition with slack s, denoted ( k, s ) -BCP, is a partition of V ( G ) into k nonempty subsets, of sizes n 1, …, n k with | n i − n / k | ≤ s, each of which induces a connected subgraph (when s = 0, the k parts are perfectly balanced, and we call it k -BCP for short). A recombination is an operation that takes a ( k, s ) -BCP of a graph G and produces another by merging two adjacent subgraphs and repartitioning them. Given two k-BCPs, A and B, of G and a slack s ≥ 0, we wish to determine whether there exists a sequence of recombinations that transform A into B via ( k, s ) -BCPs. We obtain four results related to this problem: (1) When s is unbounded, the transformation is always possible using at most 6 ( k − 1 ) recombinations. (2) If G is Hamiltonian, the transformation is possible using O ( k n ) recombinations for any s ≥ n / k, (3) there exist negative instances for s ≤ n / ( 3 k ), and (4) we show that determining whether a sequence of recombination that connects two ( k, s ) -BCP of a graph G exists is PSPACE-complete when k ∈ O ( n ε ) and s ∈ O ( n 1 − ε ), for any constant 0 < ε ≤ 1. This statement holds even for restricted settings such as when G is an edge-maximal planar graph or when k ≥ 3 and G is planar.

Details DOI

SODA Conference 2020 Conference Paper

Atomic Embeddability, Clustered Planarity, and Thickenability

  • Radoslav Fulek
  • Csaba D. Tóth

We study the atomic embeddability testing problem, which is a common generalization of clustered planarity (c-planarity, for short) and thickenability testing, and present a polynomial time algorithm for this problem, thereby giving the first polynomial time algorithm for c-planarity. C-planarity was introduced in 1995 by Feng, Cohen, and Eades as a variant of graph planarity, in which the vertex set of the input graph is endowed with a hierarchical clustering and we seek an embedding (crossing free drawing) of the graph in the plane that respects the clustering in a certain natural sense. Until now, it has been an open problem whether c-planarity can be tested efficiently, despite relentless efforts. The thickenability problem for simplicial complexes emerged in the topology of manifolds in the 1960s. A 2-dimensional simplicial complex is thickenable if it embeds in some orientable 3-dimensional manifold. Recently, Carmesin announced that thickenability can be tested in polynomial time. Our algorithm for atomic embeddability combines ideas from Carmesin's work with algorithmic tools previously developed for weak embeddability testing. We express our results purely in terms of graphs on surfaces, and rely on the machinery of topological graph theory. Finally we give a polynomial-time reduction from c-planarity to thickenability and show that a slight generalization of atomic embeddability to the setting in which clusters are toroidal graphs is NP-complete.

Details

TCS Journal 2020 Journal Article

Multi-colored spanning graphs

  • Hugo A. Akitaya
  • Maarten Löffler
  • Csaba D. Tóth

We study a problem motivated by sparse set visualization. Given n points in the plane, each labeled with one or more primary colors, a colored spanning graph (for short, CSG) is a graph in which the vertices of each primary color induce a connected subgraph. The Min-CSG problem asks for the minimum sum of edge lengths in a colored spanning graph. We show that the problem is NP-hard for k primary colors when k ≥ 3 and provide a ( 2 − 1 3 + 2 ϱ ) -approximation algorithm for k = 3 that runs in polynomial time, where ϱ is the Steiner ratio. Further, we give an O ( n ) time algorithm in the special case that the given points are collinear and k is constant.

Details DOI

SODA Conference 2020 Conference Paper

On the Cover of the Rolling Stone

  • Adrian Dumitrescu
  • Csaba D. Tóth

We construct a convex polytope of unit diameter that when placed on a horizontal surface on one of its faces, it repeatedly rolls over from one face to another until it comes to rest on some face, far away from its start position: that is, the horizontal distance between the footprints of the start and final faces can be larger than any given threshold. According to the laws of physics, the vertical distance between the center of mass of the polytope and the horizontal surface continuously decreases throughout the entire motion. The speed of the motion is irrelevant. Specifically, if the polytope is manually stopped after each tumble, the motion resumes when released (unless it stands on the final stable face). Moreover, such a polytope can be realized so that (i) it has a unique stable face, and (ii) it is an arbitrary close approximation of a unit ball. As such, this construction gives a positive answer to a question raised by Conway (1969). The arbitrarily large rolling distance property investigated here for the first time raises intriguing questions and opens new avenues for future research. Keywords perpetuum mobile rolling distance unistable polytope center of mass laws of physics

Details

TCS Journal 2020 Journal Article

Online unit covering in Euclidean space

  • Adrian Dumitrescu
  • Anirban Ghosh
  • Csaba D. Tóth

We revisit the online Unit Covering problem in higher dimensions: Given a set of n points in R d, that arrive one by one, cover the points by balls of unit radius, so as to minimize the number of balls used. In this paper, we work in R d using the Euclidean distance. (I) We give an online deterministic algorithm with competitive ratio O ( 1. 321 d ), thereby improving on the previous record, O ( 2 d d log ⁡ d ), due to Charikar et al. (2004), by an exponential factor. In particular, the competitive ratios are 5 in the plane and 12 in 3-space (the previous ratios were 7 and 21, respectively). For d = 3, the ratio of our online algorithm matches the ratio of the current best offline algorithm for the same problem due to Biniaz et al. (2017), which is remarkable (and rather unusual). (II) We show that the competitive ratio of every deterministic online algorithm for Unit Covering in R d under the L 2 norm is at least d + 1 for every d ≥ 1. This greatly improves upon the previous best lower bound, Ω ( log ⁡ d / log ⁡ log ⁡ log ⁡ d ), due to Charikar et al. (2004). (III) We generalize the above result to Unit Covering in R d under the L C norm, where C is a centrally symmetric convex body, via the illumination number. (IV) We obtain lower bounds of 4 and 5 for the competitive ratio of any deterministic algorithm for online Unit Covering in R 2 and R 3, respectively; the previous best lower bounds were 3 for both cases. (V) When the input points are from the square or hexagonal lattice in R 2, we give deterministic online algorithms for Unit Covering with an optimal competitive ratio of 3. For the cubic lattice in R 3, we give a deterministic online algorithm with a competitive ratio of 5.

Details DOI

TCS Journal 2019 Journal Article

Minimum weight connectivity augmentation for planar straight-line graphs

  • Hugo A. Akitaya
  • Rajasekhar Inkulu
  • Torrie L. Nichols
  • Diane L. Souvaine
  • Csaba D. Tóth
  • Charles R. Winston

We consider edge insertion and deletion operations that increase the connectivity of a given planar straight-line graph (PSLG), while minimizing the total edge length of the output. We show that every connected PSLG G = ( V, E ) in general position can be augmented to a 2-connected PSLG ( V, E ∪ E + ) by adding new edges of total Euclidean length ‖ E + ‖ < 2 ‖ E ‖, and this bound is the best possible. An optimal edge set E + can be computed in O ( | V | 4 ) time; however the problem becomes NP-hard when G is disconnected. Further, we show that there is a sequence of edge insertions and deletions that transforms a connected PSLG G = ( V, E ) into a planar straight-line cycle G ′ = ( V, E ′ ) such that ‖ E ′ ‖ ≤ 2 ‖ MST ( V ) ‖, and the graph remains connected with edge length below ‖ E ‖ + ‖ MST ( V ) ‖ at all stages. These bounds are the best possible.

Details DOI

MFCS Conference 2019 Conference Paper

On the Stretch Factor of Polygonal Chains

  • Ke Chen 0011
  • Adrian Dumitrescu
  • Wolfgang Mulzer
  • Csaba D. Tóth

Let P=(p_1, p_2, .. ., p_n) be a polygonal chain. The stretch factor of P is the ratio between the total length of P and the distance of its endpoints, sum_{i = 1}^{n-1} |p_i p_{i+1}|/|p_1 p_n|. For a parameter c >= 1, we call P a c-chain if |p_ip_j|+|p_jp_k| <= c|p_ip_k|, for every triple (i, j, k), 1 <= i<j<k <= n. The stretch factor is a global property: it measures how close P is to a straight line, and it involves all the vertices of P; being a c-chain, on the other hand, is a fingerprint-property: it only depends on subsets of O(1) vertices of the chain. We investigate how the c-chain property influences the stretch factor in the plane: (i) we show that for every epsilon > 0, there is a noncrossing c-chain that has stretch factor Omega(n^{1/2-epsilon}), for sufficiently large constant c=c(epsilon); (ii) on the other hand, the stretch factor of a c-chain P is O(n^{1/2}), for every constant c >= 1, regardless of whether P is crossing or noncrossing; and (iii) we give a randomized algorithm that can determine, for a polygonal chain P in R^2 with n vertices, the minimum c >= 1 for which P is a c-chain in O(n^{2. 5} polylog n) expected time and O(n log n) space.

Details

TCS Journal 2018 Journal Article

Gap-planar graphs

  • Sang Won Bae
  • Jean-Francois Baffier
  • Jinhee Chun
  • Peter Eades
  • Kord Eickmeyer
  • Luca Grilli
  • Seok-Hee Hong
  • Matias Korman

We introduce the family of k-gap-planar graphs for k ≥ 0, i. e. , graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most k of its crossings. This definition is motivated by applications in edge casing, as a k-gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We present results on the maximum density of k-gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of k-gap-planar complete graphs, and the computational complexity of recognizing k-gap-planar graphs.

Details DOI

MFCS Conference 2018 Conference Paper

Maximum Area Axis-Aligned Square Packings

  • Hugo A. Akitaya
  • Matthew D. Jones
  • David Stalfa
  • Csaba D. Tóth

Given a point set S={s_1, .. ., s_n} in the unit square U=[0, 1]^2, an anchored square packing is a set of n interior-disjoint empty squares in U such that s_i is a corner of the ith square. The reach R(S) of S is the set of points that may be covered by such a packing, that is, the union of all empty squares anchored at points in S. It is shown that area(R(S))>= 1/2 for every finite set S subset U, and this bound is the best possible. The region R(S) can be computed in O(n log n) time. Finally, we prove that finding a maximum area anchored square packing is NP-complete. This is the first hardness proof for a geometric packing problem where the size of geometric objects in the packing is unrestricted.

Details

SODA Conference 2018 Conference Paper

Recognizing Weak Embeddings of Graphs

  • Hugo A. Akitaya
  • Radoslav Fulek
  • Csaba D. Tóth

We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding φ: G → M of a graph G into a 2-manifold M maps the vertices in V ( G ) to distinct points and the edges in E ( G ) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to a common node or arc, due to data compression or low resolution. This raises the computational problem of deciding whether a given map φ: G → M comes from an embedding. A map φ: G → M is a weak embedding if it can be perturbed into an embedding ψ ε: G → M with ║φ – ψ ε ║ < ε for every ε > 0. A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kynčl [14], which reduces to solving a system of linear equations over ℤ 2. It runs in O ( π 2 ω ) ≤ O ( n 4. 75 ) time, where ω ≈ 2. 373 is the matrix multiplication exponent and n is the number of vertices and edges of G. We improve the running time to O ( n log n ). Our algorithm is also conceptually simpler than [14]: We perform a sequence of local operations that gradually “untangles” the image φ ( G ) into an embedding ψ ( G ), or reports that φ is not a weak embedding. It generalizes a recent technique developed for the case that G is a cycle and the embedding is a simple polygon [1], and combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations.

Details

MFCS Conference 2017 Conference Paper

Two-Planar Graphs Are Quasiplanar

  • Michael Hoffmann 0001
  • Csaba D. Tóth

It is shown that every 2-planar graph is quasiplanar, that is, if a simple graph admits a drawing in the plane such that every edge is crossed at most twice, then it also admits a drawing in which no three edges pairwise cross. We further show that quasiplanarity is witnessed by a simple topological drawing, that is, any two edges cross at most once and adjacent edges do not cross.

Details

TCS Journal 2016 Journal Article

On the number of anchored rectangle packings for a planar point set

  • Kevin Balas
  • Csaba D. Tóth

We consider packing axis-aligned rectangles r 1, …, r n in the unit square [ 0, 1 ] 2 such that a vertex of each rectangle r i is a given point p i (i. e. , r i is anchored at p i ). We explore the combinatorial structure of all locally maximal configurations. When the given points are the lower-left corners of the rectangles, the number of maximal packings is shown to be at most 2 n C n, where C n is the nth Catalan number. The number of maximal packings remains exponential in n when the points may be arbitrary corners of the rectangles. Both upper bounds are complemented with exponential lower bounds. Finally, we define the graph of all lower-left anchored maximal rectangle packings, where the edges correspond to elementary operations between two packings, which leads to an output sensitive algorithm for computing these packings.

Details DOI

MFCS Conference 2006 Conference Paper

Decompositions, Partitions, and Coverings with Convex Polygons and Pseudo-triangles

  • Oswin Aichholzer
  • Clemens Huemer
  • Sarah Kappes
  • Bettina Speckmann
  • Csaba D. Tóth

Abstract We propose a novel subdivision of the plane that consists of both convex polygons and pseudo-triangles. This pseudo-convex decomposition is significantly sparser than either convex decompositions or pseudo-triangulations for planar point sets and simple polygons. We also introduce pseudo-convex partitions and coverings. We establish some basic properties and give combinatorial bounds on their complexity. Our upper bounds depend on new Ramsey-type results concerning disjoint empty convex k -gons in point sets.

Details
v2026.09.13