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

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

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

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

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
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

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