DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2026.15

Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity

Authors: Sujoy Bhore, Sándor Kisfaludi‑Bak, Lazar Milenković, Csaba D. Tóth, Karol Węgrzycki, and Sampson Wong

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

A Euclidean noncrossing Steiner (1+ε)-spanner for a point set P ⊂ ℝ² is a planar straight-line graph that, for any two points a, b ∈ P, contains a path whose length is at most 1+ε times the Euclidean distance between a and b. We construct a Euclidean noncrossing Steiner (1+ε)-spanner with O(n/ε^{3/2}) edges for any set of n points in the plane. This result improves upon the previous best upper bound of O(n/ε⁴) obtained nearly three decades ago. We also establish an almost matching lower bound: There exist n points in the plane for which any Euclidean noncrossing Steiner (1+ε)-spanner has Ω_μ(n/ε^{3/2-μ}) edges for any μ > 0. Our lower bound uses recent generalizations of the Szemerédi-Trotter theorem to disk-tube incidences in geometric measure theory.

Cite as

Sujoy Bhore, Sándor Kisfaludi‑Bak, Lazar Milenković, Csaba D. Tóth, Karol Węgrzycki, and Sampson Wong. Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2026.15,
  author =	{Bhore, Sujoy and Kisfaludi‑Bak, S\'{a}ndor and Milenkovi\'{c}, Lazar and T\'{o}th, Csaba D. and W\k{e}grzycki, Karol and Wong, Sampson},
  title =	{{Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.15},
  URN =		{urn:nbn:de:0030-drops-258210},
  doi =		{10.4230/LIPIcs.SoCG.2026.15},
  annote =	{Keywords: geometric network design, spanners, crossing number, incidences}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.13

Dynamic Light Spanners in Doubling Metrics

Authors: Sujoy Bhore, Jonathan Conroy, and Arnold Filtser

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

A t-spanner of a point set X in a metric space (𝒳, δ) is a graph G with vertex set P such that, for any pair of points u,v ∈ X, the distance between u and v in G is at most t times δ(u,v). We study the problem of maintaining a spanner for a dynamic point set X - that is, when X undergoes a sequence of insertions and deletions - in a metric space of constant doubling dimension. For any constant ε > 0, we maintain a (1+ε)-spanner of P whose total weight remains within a constant factor of the weight of the minimum spanning tree of X. Each update (insertion or deletion) can be performed in poly(log Φ) time, where Φ denotes the aspect ratio of X. Prior to our work, no efficient dynamic algorithm for maintaining a light-weight spanner was known even for point sets in low-dimensional Euclidean space.

Cite as

Sujoy Bhore, Jonathan Conroy, and Arnold Filtser. Dynamic Light Spanners in Doubling Metrics. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2026.13,
  author =	{Bhore, Sujoy and Conroy, Jonathan and Filtser, Arnold},
  title =	{{Dynamic Light Spanners in Doubling Metrics}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.13},
  URN =		{urn:nbn:de:0030-drops-258193},
  doi =		{10.4230/LIPIcs.SoCG.2026.13},
  annote =	{Keywords: Dynamic data structures, spanners, light-weight, Euclidean metrics, doubling metrics}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.24

Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support

Authors: Reilly Browne and Hsien-Chih Chang

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

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.

Cite as

Reilly Browne and Hsien-Chih Chang. Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{browne_et_al:LIPIcs.SoCG.2026.24,
  author =	{Browne, Reilly and Chang, Hsien-Chih},
  title =	{{Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.24},
  URN =		{urn:nbn:de:0030-drops-258300},
  doi =		{10.4230/LIPIcs.SoCG.2026.24},
  annote =	{Keywords: Minimum dominating set, planar graphs, shallow cell complexity}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.65

Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spaces

Authors: Sándor Kisfaludi-Bak and Geert van Wordragen

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

We consider Steiner spanners in Euclidean and non-Euclidean geometries. In the Euclidean setting, a recent line of work initiated by Le and Solomon [FOCS'19] and further improved by Chang et al. [SoCG'24] obtained Steiner (1+ε)-spanners of size O_d(ε^{(1-d)/2} log(1/ε) n), nearly matching the lower bound Ω_d(ε^{(1-d)/2} n) of Bhore and Tóth [SIDMA'22]. We obtain Steiner (1+ε)-spanners of size O_d(ε^{(1-d)/2} log(1/ε)n) not only in d-dimensional Euclidean space, but also in d-dimensional spherical and hyperbolic space. For any fixed dimension d, the obtained edge count is optimal up to an O(log(1/ε)) factor in each of these spaces. Unlike earlier constructions, our Steiner spanners are based on simple quadtrees, and they can be dynamically maintained, leading to efficient data structures for dynamic approximate nearest neighbours and bichromatic closest pair. In the hyperbolic setting, we also show that 2-spanners in the hyperbolic plane must have Ω(nlog n) edges, and we obtain a 2-spanner of size O_d(nlog n) in d-dimensional hyperbolic space, matching our lower bound for any constant d. Finally, we give a Steiner spanner with additive error ε in hyperbolic space with O_d(ε^{(1-d)/2} log(α(n)/ε)n) edges, where α(n) is the inverse Ackermann function. Our techniques generalize to closed orientable surfaces of constant curvature as well as to some other quotient spaces.

Cite as

Sándor Kisfaludi-Bak and Geert van Wordragen. Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spaces. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 65:1-65:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kisfaludibak_et_al:LIPIcs.SoCG.2026.65,
  author =	{Kisfaludi-Bak, S\'{a}ndor and van Wordragen, Geert},
  title =	{{Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spaces}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{65:1--65:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.65},
  URN =		{urn:nbn:de:0030-drops-258728},
  doi =		{10.4230/LIPIcs.SoCG.2026.65},
  annote =	{Keywords: hyperbolic geometry, Steiner spanner, dynamic approximate nearest neighbours}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.68

Optimal Bounds for Spanners and Tree Covers in Doubling Metrics

Authors: An La, Hung Le, Shay Solomon, Cuong Than, Vinayak, Shuang Yang, and Tianyi Zhang

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

It is known that any n-point set in the d-dimensional Euclidean space ℝ^d, for d = O(1), admits: 1) A (1+ε)-spanner with maximum degree Õ(ε^{-d+1}) and with lightness Õ(ε^{-d}), for any ε > 0. 2) A (1+ε)-tree cover with Õ(n ⋅ ε^{-d+1}) trees and maximum degree of O(1) in each tree. Moreover, all the parameters in these constructions are optimal: For any 2 ≤ d = O(1), there exists an n-point set in ℝ^d, for which any (1+ε)-spanner has Ω̃(n⋅ε^{-d+1}) edges and lightness Ω̃(ε^{-d}). The upper bounds for Euclidean spanners rely heavily on the spatial property of cone partitioning in ℝ^d, which does not seem to extend to the wider family of doubling metrics, i.e., metric spaces of constant doubling dimension. In doubling metrics, a simple spanner construction from two decades ago, the net-tree spanner, has Õ(n⋅ε^{-d}) edges, and it could be transformed into a spanner of maximum degree Õ(ε^{-d}) and lightness Õ(n⋅ε^{-(d+1)}) by pruning redundant edges. Moreover, a careful refinement of the net-tree spanner yields a (1+ε)-tree cover with Õ(ε^{-d}) trees. Despite a large body of work, the problem of obtaining tight bounds for spanners and tree covers in the wider family of doubling metrics has remained elusive. We resolve this problem by presenting: 1) A surprisingly simple and tight lower bound, which shows that the net-tree spanner and its pruned version are optimal with respect to all the involved parameters. 2) A new construction of (1+ε)-tree covers with Õ(n⋅ε^{-d}) trees, with maximum degree O(1) in each tree. This construction is optimal with respect to the number of trees and maximum degree.

Cite as

An La, Hung Le, Shay Solomon, Cuong Than, Vinayak, Shuang Yang, and Tianyi Zhang. Optimal Bounds for Spanners and Tree Covers in Doubling Metrics. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 68:1-68:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{la_et_al:LIPIcs.SoCG.2026.68,
  author =	{La, An and Le, Hung and Solomon, Shay and Than, Cuong and Vinayak and Yang, Shuang and Zhang, Tianyi},
  title =	{{Optimal Bounds for Spanners and Tree Covers in Doubling Metrics}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{68:1--68:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.68},
  URN =		{urn:nbn:de:0030-drops-258756},
  doi =		{10.4230/LIPIcs.SoCG.2026.68},
  annote =	{Keywords: doubling metrics, doubling spanners, Euclidean spanners, tree cover}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.70

Tree-Like Shortcuttings of Trees

Authors: Hung Le, Lazar Milenković, Shay Solomon, and Cuong Than

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

Sparse shortcuttings of trees - equivalently, sparse 1-spanners for tree metrics with bounded hop-diameter - have been studied extensively (under different names and settings), since the pioneering works of [Andrew Chi-Chih Yao, 1982; Chazelle, 1987; Noga Alon and Baruch Schieber, 1987; Hans L. Bodlaender et al., 1994], initially motivated by applications to range queries, online tree product, and MST verification, to name a few. These constructions were also lifted from trees to other graph families using known low-distortion embedding results. The works of [Andrew Chi-Chih Yao, 1982; Chazelle, 1987; Noga Alon and Baruch Schieber, 1987; Hans L. Bodlaender et al., 1994] establish a tight tradeoff between hop-diameter and sparsity (or average degree) for tree shortcuttings and imply constant-hop shortcuttings for n-node trees with sparsity O(log^* n). Despite their small sparsity, all known constant-hop shortcuttings contain dense subgraphs (of sparsity Ω(log n)), which is a significant drawback for many applications. We initiate a systematic study of constant-hop tree shortcuttings that are "tree-like". We focus on two well-studied graph parameters that measure how far a graph is from a tree: arboricity and treewidth. Our contribution is twofold. - New upper and lower bounds for tree-like shortcuttings of trees, including an optimal tradeoff between hop-diameter and treewidth for all hop-diameter up to O(log log n). We also provide a lower bound for larger values of k, which together yield hop-diameter× treewidth = Ω((log log n)²) for all values of hop-diameter, resolving an open question of [Arnold Filtser and Hung Le, 2022; H. Le, 2023]. - Applications of these bounds, focusing on low-dimensional Euclidean and doubling metrics. A seminal work of Arya et al. [S. Arya et al., 1995] presented a (1+ε)-spanner with constant hop-diameter and sparsity O(log^* n), but with large arboricity. We show that constant hop-diameter is sufficient to achieve arboricity O(log^*{n}). Furthermore, we present a (1+ε)-stretch routing scheme in the fixed-port model with 3 hops and a local memory of O(log²n / log log n) bits, resolving an open question of [Omri Kahalon et al., 2022].

Cite as

Hung Le, Lazar Milenković, Shay Solomon, and Cuong Than. Tree-Like Shortcuttings of Trees. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 70:1-70:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.SoCG.2026.70,
  author =	{Le, Hung and Milenkovi\'{c}, Lazar and Solomon, Shay and Than, Cuong},
  title =	{{Tree-Like Shortcuttings of Trees}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{70:1--70:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.70},
  URN =		{urn:nbn:de:0030-drops-258776},
  doi =		{10.4230/LIPIcs.SoCG.2026.70},
  annote =	{Keywords: spanner, tree shortcutting, arboricity, treewidth}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.38

Lower Bounds on Tree Covers

Authors: Yu Chen, Zihan Tan, and Hangyu Xu

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

Given an n-point metric space (X,d_X), a tree cover 𝒯 is a set of |𝒯| = k trees on X such that every pair of vertices in X has a low-distortion path in one of the trees in 𝒯. Tree covers have been playing a crucial role in graph algorithms for decades, and the research focus is the construction of tree covers with small size k and distortion. When k = 1, the best distortion is known to be Θ(n). For a constant k ≥ 2, the best distortion upper bound is Õ(n^{1/k}) and the strongest lower bound is Ω(log_k n), leaving a gap to be closed. In this paper, we improve the lower bound to Ω(n^{1/(2^{k-1)}}). Our proof is a novel analysis on a structurally simple grid-like graph, which utilizes some combinatorial fixed-point theorems. We believe that they will prove useful for analyzing other tree-like data structures as well.

Cite as

Yu Chen, Zihan Tan, and Hangyu Xu. Lower Bounds on Tree Covers. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ITCS.2026.38,
  author =	{Chen, Yu and Tan, Zihan and Xu, Hangyu},
  title =	{{Lower Bounds on Tree Covers}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.38},
  URN =		{urn:nbn:de:0030-drops-253254},
  doi =		{10.4230/LIPIcs.ITCS.2026.38},
  annote =	{Keywords: Tree Covers, Combinatorial Fixed-Point Theorems}
}

Document

DOI: 10.4230/DagRep.15.5.134

Metric Sketching and Dynamic Algorithms for Geometric and Topological Graphs (Dagstuhl Seminar 25212)

Authors: Sujoy Bhore, Jie Gao, Hung Le, Csaba D. Tóth, and Lazar Milenković

Published in: Dagstuhl Reports, Volume 15, Issue 5 (2025)

Abstract

Sketching is a basic technique to handle big data: Compress a big input dataset into a small dataset, called a sketch, that (approximately) preserves the important information in the input dataset. A metric space is often given as a distance matrix with Ω(n²) entries, and metric sketching techniques aim to reduce the space to linear. One goal of this Dagstuhl Seminar was to understand different sketching techniques and metric spaces that admit small sketches. Another common approach to handling big datasets is dynamic algorithms. Typically, large datasets do not arrive in a single batch; instead, they are updated over time in small increments. The objective of dynamic algorithms is to respond to data updates quickly, ideally with an update time that is polylogarithmic in the size of the whole dataset. In this Dagstuhl Seminar "Metric Sketching and Dynamic Algorithms for Geometric and Topological Graphs" (25212), we considered sketching and dynamic algorithms in the context of geometric intersection graphs and topological graphs. Geometric intersection graphs have been used to model many real-world massive graphs, such as wireless networks. Topological graphs, including planar graphs, have been used in applications such as geographic information systems and motion planning. While geometric intersection graphs and topological graphs are seemingly different, they have common structural properties that allow the transfer of algorithmic techniques between the two domains, which was the motivation of this seminar: Uncovering deeper connections between metric sketching, dynamic algorithms, geometric intersection graphs, and topological graphs. More concretely, we studied: (1) the construction of sketching structures, such as spanners, tree covers, distance oracles, and emulators with optimal parameters for various metrics and graphs, including geometric and topological graphs; (2) dynamic problems in geometric intersections graphs, including connectivity, spanners, shortest paths; and (3) dynamic maintenance of metric sketching structures in topological graphs.

Cite as

Sujoy Bhore, Jie Gao, Hung Le, Csaba D. Tóth, and Lazar Milenković. Metric Sketching and Dynamic Algorithms for Geometric and Topological Graphs (Dagstuhl Seminar 25212). In Dagstuhl Reports, Volume 15, Issue 5, pp. 134-157, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{bhore_et_al:DagRep.15.5.134,
  author =	{Bhore, Sujoy and Gao, Jie and Le, Hung and T\'{o}th, Csaba D. and Milenkovi\'{c}, Lazar},
  title =	{{Metric Sketching and Dynamic Algorithms for Geometric and Topological Graphs (Dagstuhl Seminar 25212)}},
  pages =	{134--157},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2025},
  volume =	{15},
  number =	{5},
  editor =	{Bhore, Sujoy and Gao, Jie and Le, Hung and T\'{o}th, Csaba D. and Milenkovi\'{c}, Lazar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.15.5.134},
  URN =		{urn:nbn:de:0030-drops-252753},
  doi =		{10.4230/DagRep.15.5.134},
  annote =	{Keywords: geometric spanners, geometric intersection graphs, planar metrics, metric covering, computational geometry}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.39

Going Beyond Surfaces in Diameter Approximation

Authors: Michał Włodarczyk

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

Calculating the diameter of an undirected graph requires quadratic running time under the Strong Exponential Time Hypothesis and this barrier works even against any approximation better than 3/2. For planar graphs with positive edge weights, there are known (1+ε)-approximation algorithms with running time poly(1/ε, log n)⋅ n. However, these algorithms rely on shortest path separators and this technique falls short to yield efficient algorithms beyond graphs of bounded genus. In this work we depart from embedding-based arguments and obtain diameter approximations relying on VC set systems and the local treewidth property. We present two orthogonal extensions of the planar case by giving (1+ε)-approximation algorithms with the following running times: - 𝒪_h((1/ε)^𝒪(h) ⋅ nlog² n)-time algorithm for graphs excluding an apex graph of size h as a minor, - 𝒪_d((1/ε)^𝒪(d) ⋅ nlog² n)-time algorithm for the class of d-apex graphs. As a stepping stone, we obtain efficient (1+ε)-approximate distance oracles for graphs excluding an apex graph of size h as a minor. Our oracle has preprocessing time 𝒪_h((1/ε)⁸⋅ nlog nlog W) and query time 𝒪_h((1/ε)²⋅log n log W), where W is the metric stretch. Such oracles have been so far only known for bounded genus graphs. All our algorithms are deterministic.

Cite as

Michał Włodarczyk. Going Beyond Surfaces in Diameter Approximation. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wlodarczyk:LIPIcs.ESA.2025.39,
  author =	{W{\l}odarczyk, Micha{\l}},
  title =	{{Going Beyond Surfaces in Diameter Approximation}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{39:1--39:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.39},
  URN =		{urn:nbn:de:0030-drops-245076},
  doi =		{10.4230/LIPIcs.ESA.2025.39},
  annote =	{Keywords: diameter, approximation, distance oracles, graph minors, treewidth}
}

Document

Invited Talk

DOI: 10.4230/LIPIcs.WADS.2025.2

Unintuitive Facts About Distances on Planar Graphs (Invited Talk)

Authors: Hsien-Chih Chang

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

Conventional wisdom told us that planar graphs are essentially edge-weighted grids, with more or less equal side-lengths. An n-node n^{1/2}-by-n^{1/2} square grid has treewidth Θ(n^{1/2}); and if we want to preserve shortest-path distances between every pair of boundary nodes, intuitively we have to keep all the n^{1/2} column and row paths, which together create n "crossings" that cannot be removed. This seems to suggest that planar graphs are incompressible and not tree-like. Or does it? In this talk we will discuss three unintuitive, and perhaps surprising, facts about planar metrics in the (1+ε)-approximation regime. First we demonstrate how to construct emulator for planar graphs that preserves all-pair distances between k terminals, and has size Õ_ε(k). (This implies, for the grid example above, the resulting emulator has size Õ(n^{1/2}).) Second, planar metrics can be covered using constantly(!) many trees, in the sense that we can construct O(1) many trees independent to the size of the input graph that never shrinks distances, so that given any pair of nodes x and y, there is one tree T that contains both x and y whose distance on T is stretched by at most a 1+ε factor. Along the way we will introduce a novel structure on planar metrics - the gridtrees - that enables such tree covers, as well as its applications in the resolution to the Steiner point removal problem, and in constructing embeddings of planar graphs into polylog-treewidth graphs with (1+ε)-distortion. (Which means, if we are willing to distort the distance by a small amount, planar metrics are very much tree-like.) Finally, we will discuss the issue of spanning. Both results above rely on the fact that the emulator and the tree cover use "Steiner nodes", which are nodes not presented in the original input graph. Maybe this is cheating, and the distance compression is only possible because of these nodes that appear out of nowhere? Our goal is to convince you otherwise: We can in fact construct emulators for planar graphs that are minors, which only uses paths and edges from the input planar graph; and in the case of tree covers, we are one or two new structures away from enforcing the trees to be spanning, that is, the edges in the trees have come from the input graph as well.

Cite as

Hsien-Chih Chang. Unintuitive Facts About Distances on Planar Graphs (Invited Talk). In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chang:LIPIcs.WADS.2025.2,
  author =	{Chang, Hsien-Chih},
  title =	{{Unintuitive Facts About Distances on Planar Graphs}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.2},
  URN =		{urn:nbn:de:0030-drops-242338},
  doi =		{10.4230/LIPIcs.WADS.2025.2},
  annote =	{Keywords: planar, emulator, tree cover, gridtree, spanning, sparsifier, tree embedding, clustering, Baker's technique, KPR decomposition, low-diameter decomposition, quadtree, shortest-path separator, portal}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.30

Light Spanners with Small Hop-Diameter

Authors: Sujoy Bhore and Lazar Milenković

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

Lightness, sparsity, and hop-diameter are the fundamental parameters of geometric spanners. Arya et al. [STOC'95] showed in their seminal work that there exists a construction of Euclidean (1+ε)-spanners with hop-diameter O(log n) and lightness O(log n). They also gave a general tradeoff of hop-diameter k and sparsity O(α_k(n)), where α_k is a very slowly growing inverse of an Ackermann-style function. The former combination of logarithmic hop-diameter and lightness is optimal due to the lower bound by Dinitz et al. [FOCS'08]. Later, Elkin and Solomon [STOC'13] generalized the light spanner construction to doubling metrics and extended the tradeoff for more values of hop-diameter k. In a recent line of work [SoCG'22, SoCG'23], Le et al. proved that the aforementioned tradeoff between the hop-diameter and sparsity is tight for every choice of hop-diameter k. A fundamental question remains: What is the optimal tradeoff between the hop-diameter and lightness for every value of k? In this paper, we present a general framework for constructing light spanners with small hop-diameter. Our framework is based on tree covers. In particular, we show that if a metric admits a tree cover with γ trees, stretch t, and lightness L, then it also admits a t-spanner with hop-diameter k and lightness O(kn^{2/k}⋅ γ L). Further, we note that the tradeoff for trees is tight due to a construction in uniform line metric, which is perhaps the simplest tree metric. As a direct consequence of this framework, we obtain new tradeoffs between lightness and hop-diameter for doubling metrics.

Cite as

Sujoy Bhore and Lazar Milenković. Light Spanners with Small Hop-Diameter. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.ICALP.2025.30,
  author =	{Bhore, Sujoy and Milenkovi\'{c}, Lazar},
  title =	{{Light Spanners with Small Hop-Diameter}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{30:1--30:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.30},
  URN =		{urn:nbn:de:0030-drops-234075},
  doi =		{10.4230/LIPIcs.ICALP.2025.30},
  annote =	{Keywords: Geometric Spanners, Lightness, Hop-Diameter, Recurrences, Lower Bounds}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2025.49

On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and Other Applications

Authors: Arnold Filtser

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

Given a metric space (X,d_X), a (β,s,Δ)-sparse cover is a collection of clusters 𝒞 ⊆ P(X) with diameter at most Δ, such that for every point x ∈ X, the ball B_X(x,Δ/β) is fully contained in some cluster C ∈ 𝒞, and x belongs to at most s clusters in 𝒞. Our main contribution is to show that the shortest path metric of every K_r-minor free graphs admits (O(r),O(r²),Δ)-sparse cover, and for every ε > 0, (4+ε,O(1/ε)^r,Δ)-sparse cover (for arbitrary Δ > 0). We then use this sparse cover to show that every K_r-minor free graph embeds into 𝓁_∞^{Õ(1/ε)^{r+1}⋅log n} with distortion 3+ε (resp. into 𝓁_∞^{Õ(r²)⋅log n} with distortion O(r)). Further, among other applications, this sparse cover immediately implies an algorithm for the oblivious buy-at-bulk problem in fixed minor free graphs with the tight approximation factor O(log n) (previously nothing beyond general graphs was known).

Cite as

Arnold Filtser. On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and Other Applications. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{filtser:LIPIcs.SoCG.2025.49,
  author =	{Filtser, Arnold},
  title =	{{On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and Other Applications}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{49:1--49:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.49},
  URN =		{urn:nbn:de:0030-drops-232015},
  doi =		{10.4230/LIPIcs.SoCG.2025.49},
  annote =	{Keywords: Sparse cover, minor free graphs, metric embeddings, 𝓁\underline∞, oblivious buy-at-bulk}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2024.37

Optimal Euclidean Tree Covers

Authors: Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenković, Shay Solomon, and Cuong Than

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract

A (1+e)-stretch tree cover of a metric space is a collection of trees, where every pair of points has a (1+e)-stretch path in one of the trees. The celebrated Dumbbell Theorem [Arya et al. STOC'95] states that any set of n points in d-dimensional Euclidean space admits a (1+e)-stretch tree cover with O_d(e^{-d} ⋅ log(1/e)) 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 ⋅ log(1/e)/e^d + n ⋅ e^{-2d}). Since the same point may occur in multiple levels of the tree, the 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+e)-stretch tree cover with O_d(e^{-d+1} ⋅ log(1/e)) trees, which is optimal (up to the log(1/e) factor). Moreover, the maximum degree of points in any tree is an 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+e)-stretch Steiner tree cover (that may use Steiner points) with O_d(e^{(-d+1)/2} ⋅ log(1/e)) 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.

Cite as

Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenković, Shay Solomon, and Cuong Than. Optimal Euclidean Tree Covers. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.SoCG.2024.37,
  author =	{Chang, Hsien-Chih and Conroy, Jonathan and Le, Hung and Milenkovi\'{c}, Lazar and Solomon, Shay and Than, Cuong},
  title =	{{Optimal Euclidean Tree Covers}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.37},
  URN =		{urn:nbn:de:0030-drops-199828},
  doi =		{10.4230/LIPIcs.SoCG.2024.37},
  annote =	{Keywords: Tree cover, spanner, Steiner point, routing, bounded-degree, quadtree, net-tree}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2023.47

Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function

Authors: Hung Le, Lazar Milenković, and Shay Solomon

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract

In STOC'95 [S. Arya et al., 1995] Arya et al. showed that any set of n points in ℝ^d admits a (1+ε)-spanner with hop-diameter at most 2 (respectively, 3) and O(n log n) edges (resp., O(n log log n) edges). They also gave a general upper bound tradeoff of hop-diameter k with O(n α_k(n)) edges, for any k ≥ 2. The function α_k is the inverse of a certain Ackermann-style function, where α₀(n) = ⌈n/2⌉, α₁(n) = ⌈√n⌉, α₂(n) = ⌈log n⌉, α₃(n) = ⌈log log n⌉, α₄(n) = log^* n, α₅(n) = ⌊ 1/2 log^*n ⌋, …. Roughly speaking, for k ≥ 2 the function α_{k} is close to ⌊(k-2)/2⌋-iterated log-star function, i.e., log with ⌊(k-2)/2⌋ stars. Despite a large body of work on spanners of bounded hop-diameter, the fundamental question of whether this tradeoff between size and hop-diameter of Euclidean (1+ε)-spanners is optimal has remained open, even in one-dimensional spaces. Three lower bound tradeoffs are known: - An optimal k versus Ω(n α_k(n)) by Alon and Schieber [N. Alon and B. Schieber, 1987], but it applies to stretch 1 (not 1+ε). - A suboptimal k versus Ω(nα_{2k+6}(n)) by Chan and Gupta [H. T.-H. Chan and A. Gupta, 2006]. - A suboptimal k versus Ω(n/(2^{6⌊k/2⌋}) α_k(n)) by Le et al. [Le et al., 2022]. This paper establishes the optimal k versus Ω(n α_k(n)) lower bound tradeoff for stretch 1+ε, for any ε > 0, and for any k. An important conceptual contribution of this work is in achieving optimality by shaving off an extremely slowly growing term, namely 2^{6⌊k/2⌋} for k ≤ O(α(n)); such a fine-grained optimization (that achieves optimality) is very rare in the literature. To shave off the 2^{6⌊k/2⌋} term from the previous bound of Le et al., our argument has to drill much deeper. In particular, we propose a new way of analyzing recurrences that involve inverse-Ackermann style functions, and our key technical contribution is in presenting the first explicit construction of concave versions of these functions. An important advantage of our approach over previous ones is its robustness: While all previous lower bounds are applicable only to restricted 1-dimensional point sets, ours applies even to random point sets in constant-dimensional spaces.

Cite as

Hung Le, Lazar Milenković, and Shay Solomon. Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.SoCG.2023.47,
  author =	{Le, Hung and Milenkovi\'{c}, Lazar and Solomon, Shay},
  title =	{{Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.47},
  URN =		{urn:nbn:de:0030-drops-178976},
  doi =		{10.4230/LIPIcs.SoCG.2023.47},
  annote =	{Keywords: Euclidean spanners, Ackermann functions, convex functions, hop-diameter}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2022.54

Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound

Authors: Hung Le, Lazar Milenković, and Shay Solomon

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract

In STOC'95 [ADMSS95] Arya et al. showed that any set of n points in R^d admits a (1+ε)-spanner with hop-diameter at most 2 (respectively, 3) and O(n log n) edges (resp., O(n log log n) edges). They also gave a general upper bound tradeoff of hop-diameter at most k and O(n α_k(n)) edges, for any k≥2. The function α_k is the inverse of a certain Ackermann-style function at the ⌊k/2⌋th level of the primitive recursive hierarchy, where α₀(n)=⌈n/2⌉, α₁(n)=⌈√n⌉, α₂(n)=⌈log n⌉, α₃(n)=⌈log log n⌉, α₄(n)=log^* n, α₅(n)=⌊1/2 log^*n⌋, .... Roughly speaking, for k≥2 the function α_{k} is close to ⌊(k-2)/2⌋-iterated log-star function, i.e., log with ⌊(k-2)/2⌋ stars. Also, α_{2α(n)+4}(n)≤4, where α(n) is the one-parameter inverse Ackermann function, which is an extremely slowly growing function. Whether or not this tradeoff is tight has remained open, even for the cases k=2 and k=3. Two lower bounds are known: The first applies only to spanners with stretch 1 and the second is sub-optimal and applies only to sufficiently large (constant) values of k. In this paper we prove a tight lower bound for any constant k: For any fixed ε>0, any (1+ε)-spanner for the uniform line metric with hop-diameter at most k must have at least Ω(n α_k(n)) edges.

Cite as

Hung Le, Lazar Milenković, and Shay Solomon. Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 54:1-54:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.SoCG.2022.54,
  author =	{Le, Hung and Milenkovi\'{c}, Lazar and Solomon, Shay},
  title =	{{Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{54:1--54:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.54},
  URN =		{urn:nbn:de:0030-drops-160629},
  doi =		{10.4230/LIPIcs.SoCG.2022.54},
  annote =	{Keywords: Euclidean spanners, hop-diameter, inverse-Ackermann, lower bounds, sparse spanners}
}

16 Search Results for "Milenković, Lazar"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message