60 Search Results for "Le, Hung"

Document
DOI: 10.4230/LIPIcs.SoCG.2026.29
Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above

Authors: Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng

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

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

Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng. Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.SoCG.2026.29,
  author =	{Chan, Timothy M. and Chang, Hsien-Chih and Gao, Jie and Kisfaludi-Bak, S\'{a}ndor and Le, Hung and Zheng, Da Wei},
  title =	{{Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{29:1--29: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.29},
  URN =		{urn:nbn:de:0030-drops-258357},
  doi =		{10.4230/LIPIcs.SoCG.2026.29},
  annote =	{Keywords: Graph Diameter, Geometric Intersection Graphs, Unit Ball Graphs}
}
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 Õ(ε^{-d+1}) and with lightness Õ(ε^{-d}), for any ε > 0. 2) A (1+ε)-tree cover with Õ(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 Õ(n⋅ε^{-d}) edges, and it could be transformed into a spanner of maximum degree Õ(ε^{-d}) and lightness Õ(n⋅ε^{-(d+1)}) by pruning redundant edges. Moreover, a careful refinement of the net-tree spanner yields a (1+ε)-tree cover with Õ(ε^{-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 Õ(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.SoCG.2026.71
Approximating Euclidean Shallow-Light Trees

Authors: Hung Le, Shay Solomon, Cuong Than, Csaba D. Tóth, and Tianyi Zhang

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

Abstract
For a weighted graph G = (V, E, w) and a designated source vertex s ∈ V, a spanning tree that simultaneously approximates a shortest-path tree w.r.t. source s and a minimum spanning tree is called a shallow-light tree (SLT). Specifically, an (α, β)-SLT of G w.r.t. s ∈ V is a spanning tree of G with root-stretch α (preserving all distances between s and all other vertices up to a factor of α) and lightness β (its weight is at most β times the weight of a minimum spanning tree of G). It was shown in the early 1990s that (1) for any graph, any source, and any ε > 0, there is a (1 + ε, O(1/ε))-SLT, and (2) there exist graphs for which β = Ω(1/ε) for any (1+ε,β)-SLT. The focus of this work is on SLTs in low-dimensional Euclidean spaces, which are of special interest for some applications of SLTs, in geometric network optimization problems. The aforementioned existential lower bound applies to Euclidean plane, as well. It was shown more than a decade ago that (1) by using Steiner points, one can reduce the lightness bound from O(1/ε) to O(√{1/ε}), and (2) there exist point sets in the plane for which β = Ω(√{1/ε}) for any Steiner (1+ε,β)-SLT. These tight existential bounds for the Euclidean case yield approximation factors of O(1/ε) and O(√{1/ε}) on the minimum weight of any non-Steiner and Steiner tree with root-stretch 1+ε, respectively. Despite the large body of work on SLTs, the basic question of whether a better approximation algorithm exists was left untouched to date, and this holds in any graph family. This paper makes a first nontrivial step towards resolving this question by presenting two bicriteria approximation algorithms. For any ε > 0, a set P of n points in constant-dimensional Euclidean space and a source s ∈ P, our first (respectively, second) algorithm returns, in O(n log n ⋅ polylog(ε^{-1})) time, a non-Steiner (resp., Steiner) tree with root-stretch 1+O(ε log ε^{-1}) and weight at most O(opt_ε ⋅ log² ε^{-1}) (resp., O(opt_ε ⋅ log ε^{-1})), where opt_ε denotes the minimum weight of a non-Steiner (resp., Steiner) tree with root-stretch 1+ε.
Cite as

Hung Le, Shay Solomon, Cuong Than, Csaba D. Tóth, and Tianyi Zhang. Approximating Euclidean Shallow-Light Trees. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 71:1-71:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.SoCG.2026.71,
  author =	{Le, Hung and Solomon, Shay and Than, Cuong and T\'{o}th, Csaba D. and Zhang, Tianyi},
  title =	{{Approximating Euclidean Shallow-Light Trees}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{71:1--71: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.71},
  URN =		{urn:nbn:de:0030-drops-258789},
  doi =		{10.4230/LIPIcs.SoCG.2026.71},
  annote =	{Keywords: geometric network design, optimization, shallow-light tree, Steiner point}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.73
Colouring Probe H-Free Graphs

Authors: Daniël Paulusma, Johannes Rauch, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
The NP-complete problems Colouring and k-Colouring (k ≥ 3) are well studied on H-free graphs, i.e., graphs that do not contain some fixed graph H as an induced subgraph. We research to what extent the known polynomial-time algorithms for H-free graphs can be generalized if we only know some of the edges of the input graph. We do this by considering the classical probe graph model introduced in the early nineties. For a graph H, a partitioned probe H-free graph (G,P,N) consists of a graph G = (V,E), together with a set P ⊆ V of probes and an independent set N = V ⧵ P of non-probes, such that G+F is H-free for some edge set F ⊆ binom(N,2). We show the following: - We fully classify Colouring on partitioned probe H-free graphs and show that the obtained complexity dichotomy differs from the known dichotomy of Colouring for H-free graphs. - We fully classify 3-Colouring on partitioned probe P_t-free graphs: we prove polynomial-time solvability for t ≤ 5 and NP-completeness for t ≥ 6. In contrast, 3-Colouring on P_t-free graphs is known to be polynomial-time solvable for t ≤ 7 and quasi-polynomial-time solvable for t ≥ 8. Our main result is our polynomial-time algorithm for 3-Colouring on partitioned P₅-free graphs. For this result, and also for all our other polynomial-time results, we do not need to know the edge set F; we only need to know its existence. Moreover, the class of probe P₅-free graphs includes not only paths of arbitrary length but even all bipartite graphs and is much richer than the class of P₅-free graphs. The latter is also evidenced by the fact that there exist graph problems, such as Matching Cut, that are known to be polynomial-time solvable for P₅-free graphs but NP-complete for partitioned probe P₅-free graphs. In particular, unlike the class of 3-colourable P₅-free graphs, the class of 3-colourable probe P₅-free graphs has unbounded mim-width. Hence, our polynomial-time result for 3-Colouring for probe P₅-free graphs suggests that there may be another, deeper overarching reason why 3-Colouring is polynomial-time solvable for P₅-free graphs.
Cite as

Daniël Paulusma, Johannes Rauch, and Erik Jan van Leeuwen. Colouring Probe H-Free Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 73:1-73:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{paulusma_et_al:LIPIcs.STACS.2026.73,
  author =	{Paulusma, Dani\"{e}l and Rauch, Johannes and van Leeuwen, Erik Jan},
  title =	{{Colouring Probe H-Free Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{73:1--73:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.73},
  URN =		{urn:nbn:de:0030-drops-255621},
  doi =		{10.4230/LIPIcs.STACS.2026.73},
  annote =	{Keywords: colouring, probe graph, forbidden induced subgraph, complexity dichotomy}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.74
List Coloring Ordered Graphs with Forbidden Induced Subgraphs

Authors: Marta Piecyk and Paweł Rzążewski

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
In the List k-Coloring problem we are given a graph whose every vertex is equipped with a list, which is a subset of {1,…,k}. We need to decide if G admits a proper coloring, where every vertex receives a color from its list. The complexity of the problem in classes defined by forbidding induced subgraphs is a widely studied topic in algorithmic graph theory. Recently, Hajebi, Li, and Spirkl [SIAM J. Discr. Math. 38 (2024)] initiated the study of List 3-Coloring in ordered graphs, i.e., graphs with fixed linear ordering of vertices. Forbidding ordered induced subgraphs allows us to investigate the boundary of tractability more closely. We continue this direction of research, focusing mostly on the case of List 4-Coloring. We present several algorithmic and hardness results, which altogether provide an almost complete dichotomy for classes defined by forbidding one fixed ordered graph: our investigations leave one minimal open case.
Cite as

Marta Piecyk and Paweł Rzążewski. List Coloring Ordered Graphs with Forbidden Induced Subgraphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 74:1-74:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{piecyk_et_al:LIPIcs.STACS.2026.74,
  author =	{Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{List Coloring Ordered Graphs with Forbidden Induced Subgraphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{74:1--74:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.74},
  URN =		{urn:nbn:de:0030-drops-255634},
  doi =		{10.4230/LIPIcs.STACS.2026.74},
  annote =	{Keywords: coloring, ordered graphs, forbidden induced subgraphs}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.107
New Greedy Spanners and Applications

Authors: Elizaveta Popova and Elad Tzalik

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

Abstract
We present a simple greedy procedure to compute an (α,β)-spanner for a graph G. We then show that this procedure is useful for building fault-tolerant spanners, as well as spanners for weighted graphs. Our first main result is an algorithm that, given a multigraph G, outputs an f edge fault-tolerant (k,k-1)-spanner H of size O(fn^{1+1/k}) which is tight. To our knowledge, this is the first tight result concerning the price of fault tolerance in spanners which are not multiplicative, in any model of faults. Our second main result is a new construction of a spanner for weighted graphs. We show that any weighted graph G has a subgraph H with O(n^{1+1/k}) edges such that any path P of hop-length 𝓁 in G has a replacement path P' in H of weighted length ≤ w(P)+(2k-2)w^(1/2)(P) where w(P) is the total edge weight of P, and w^(1/2) denotes the sum of the largest ⌈𝓁/2⌉ edge weights along P. Moreover, we show such approximation is optimal for shortest paths of hop-length 2. To our knowledge, this is the first construction of a "spanner" for weighted graphs that strictly improves upon the stretch of multiplicative (2k-1)-spanners for all non-adjacent vertex pairs, while maintaining the same size bound. Our technique is based on using clustering and ball-growing, which are methods commonly used in designing spanner algorithms, to analyze simple greedy algorithms. This allows us to combine the flexibility of clustering approaches with the unique properties of the greedy algorithm to get improved bounds. In particular, our methods give a very short proof that the parallel greedy spanner adds O(kn^{1+1/k}) edges, improving upon known bounds.
Cite as

Elizaveta Popova and Elad Tzalik. New Greedy Spanners and Applications. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 107:1-107:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{popova_et_al:LIPIcs.ITCS.2026.107,
  author =	{Popova, Elizaveta and Tzalik, Elad},
  title =	{{New Greedy Spanners and Applications}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{107:1--107:25},
  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.107},
  URN =		{urn:nbn:de:0030-drops-253945},
  doi =		{10.4230/LIPIcs.ITCS.2026.107},
  annote =	{Keywords: Graph Spanners, Greedy Algorithms}
}
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/LIPIcs.OPODIS.2025.19
Orientation Does Not Help with 3-Coloring a Grid in Online-LOCAL

Authors: Thomas Boudier, Filippo Casagrande, Avinandan Das, Massimo Equi, Henrik Lievonen, Augusto Modanese, and Ronja Stimpert

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
The online-LOCAL and SLOCAL models are extensions of the LOCAL model where nodes are processed in a sequential but potentially adversarial order. So far, the only problem we know of where the global memory of the online-LOCAL model has an advantage over SLOCAL is 3-coloring bipartite graphs. Recently, Chang et al. [PODC 2024] showed that even in grids, 3-coloring requires Ω(log n) locality in deterministic online-LOCAL. This result was subsequently extended by Akbari et al. [STOC 2025] to also hold in randomized online-LOCAL. However, both proofs heavily rely on the assumption that the algorithm does not have access to the orientation of the underlying grid. In this paper, we show how to lift this requirement and obtain the same lower bound (against either model) even when the algorithm is explicitly given a globally consistent orientation of the grid.
Cite as

Thomas Boudier, Filippo Casagrande, Avinandan Das, Massimo Equi, Henrik Lievonen, Augusto Modanese, and Ronja Stimpert. Orientation Does Not Help with 3-Coloring a Grid in Online-LOCAL. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{boudier_et_al:LIPIcs.OPODIS.2025.19,
  author =	{Boudier, Thomas and Casagrande, Filippo and Das, Avinandan and Equi, Massimo and Lievonen, Henrik and Modanese, Augusto and Stimpert, Ronja},
  title =	{{Orientation Does Not Help with 3-Coloring a Grid in Online-LOCAL}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.19},
  URN =		{urn:nbn:de:0030-drops-251925},
  doi =		{10.4230/LIPIcs.OPODIS.2025.19},
  annote =	{Keywords: coloring, locally checkable labeling problems, online algorithms}
}
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.FSTTCS.2025.40
Improved Upper Bounds on Multiflow-Multicut Gaps in Cactus Graphs

Authors: Sina Kalantarzadeh and Nikhil Kumar

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
Given a set of source-sink pairs, the maximum multiflow problem asks for the largest total amount of flow that can be feasibly routed between them. The minimum multicut problem, which is dual to multiflow, seeks the lowest-cost set of edges whose removal disconnects all source-sink pairs. It is straightforward to see that the value of a minimum multicut is at least that of the corresponding maximum multiflow. The ratio between the two is known as the multiflow-multicut gap. The classical max-flow min-cut theorem tells us that this gap is exactly one when there is only a single source-sink pair. However, for multiple source-sink pairs, the gap can be arbitrarily large. In this work, we investigate the multiflow-multicut gap in cactus graphs, and establish the following results (i) tight upper bound of 1.5 for cycle (ii) an upper bound of 2 + 2/(ln 2) < 3.45 for general cactus graph (iii) tight upper bound of 2 for unicyclic graphs, where the graph contains exactly one cycle (iv) tight upper bound of 2 for path cactus graphs, where cycles are arranged along a single path. We develop novel generalizations of the classical rounding algorithm to establish our results.
Cite as

Sina Kalantarzadeh and Nikhil Kumar. Improved Upper Bounds on Multiflow-Multicut Gaps in Cactus Graphs. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 40:1-40:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kalantarzadeh_et_al:LIPIcs.FSTTCS.2025.40,
  author =	{Kalantarzadeh, Sina and Kumar, Nikhil},
  title =	{{Improved Upper Bounds on Multiflow-Multicut Gaps in Cactus Graphs}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{40:1--40:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.40},
  URN =		{urn:nbn:de:0030-drops-251205},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.40},
  annote =	{Keywords: Approximation Algorithms, Randomized Algorithms, Linear Programming, Graph Algorithms, Multicut, Multicommodity flow}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.3
Circle-Segment Intersection Queries in Connected Geometric Graphs

Authors: Peyman Afshani, Yannick Bosch, and Sabine Storandt

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
In this paper, we study the problem of efficiently reporting all intersections between a given set of line segments in the plane and a query circle, focusing on the case where the segments form the edges of a connected geometric graph. While previous data structures for circle-segment intersection queries on general segment sets incur high space or query time costs, we exploit the connectivity of the input to obtain significantly improved performance. In fact, we propose a new circle-segment intersection data structure that can be constructed in 𝒪((n + C) log³ n) time and space on connected graphs with n edges and C edge crossings. It answers intersection queries in 𝒪(k log³ n) time, where k denotes the output size. Our method relies on the construction of efficient circle-graph intersection oracles as well as a novel linear-time algorithm to partition the edges of the graph into balanced, connected components, which might be of independent interest. In a proof-of-concept experimental study on real-world road networks, we show that our novel data structure also performs well in practice. Even on networks with millions of edges, the construction time is within minutes and queries are answered in a few milliseconds.
Cite as

Peyman Afshani, Yannick Bosch, and Sabine Storandt. Circle-Segment Intersection Queries in Connected Geometric Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.ISAAC.2025.3,
  author =	{Afshani, Peyman and Bosch, Yannick and Storandt, Sabine},
  title =	{{Circle-Segment Intersection Queries in Connected Geometric Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.3},
  URN =		{urn:nbn:de:0030-drops-249114},
  doi =		{10.4230/LIPIcs.ISAAC.2025.3},
  annote =	{Keywords: Intersection data structure, Graph partitioning, Dobkin-Kirkpatrick hierarchy}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.16
A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth

Authors: Sergio Cabello, Alexander Dobler, Gašper Fijavž, Thekla Hamm, and Mirko H. Wagner

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
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 𝒮 of crossing types gives a recognition problem: does a given graph admit an 𝒮-restricted drawing, that is, a 1-planar drawing where the crossing type of each crossing is in 𝒮? We show that there is a set 𝒮_bad with three crossing types and the following properties: - If 𝒮 contains no crossing type from 𝒮_bad, then the recognition of graphs that admit an 𝒮-restricted drawing is fixed-parameter tractable with respect to the treewidth of the input graph. - If 𝒮 contains any crossing type from 𝒮_bad, then it is NP-hard to decide whether a graph has an 𝒮-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.
Cite as

Sergio Cabello, Alexander Dobler, Gašper Fijavž, Thekla Hamm, and Mirko H. Wagner. A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.ISAAC.2025.16,
  author =	{Cabello, Sergio and Dobler, Alexander and Fijav\v{z}, Ga\v{s}per and Hamm, Thekla and Wagner, Mirko H.},
  title =	{{A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.16},
  URN =		{urn:nbn:de:0030-drops-249248},
  doi =		{10.4230/LIPIcs.ISAAC.2025.16},
  annote =	{Keywords: 1-planar, crossing type, treewidth, pathwidth}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.20
Sparse Induced Subgraphs in P₇-Free Graphs of Bounded Clique Number

Authors: Maria Chudnovsky, Jadwiga Czyżewska, Kacper Kluk, Marcin Pilipczuk, and Paweł Rzążewski

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Many natural computational problems, including e.g. Max Weight Independent Set, Feedback Vertex Set, or Vertex Planarization, can be unified under an umbrella of finding the largest sparse induced subgraph that satisfies some property definable in CMSO₂ logic. It is believed that each problem expressible with this formalism can be solved in polynomial time in graphs that exclude a fixed path as an induced subgraph. This belief is supported by the existence of a quasipolynomial-time algorithm by Gartland, Lokshtanov, Pilipczuk, Pilipczuk, and Rzążewski [STOC 2021], and a recent polynomial-time algorithm for P₆-free graphs by Chudnovsky, McCarty, Pilipczuk, Pilipczuk, and Rzążewski [SODA 2024]. In this work we extend polynomial-time tractability of all such problems to P₇-free graphs of bounded clique number.
Cite as

Maria Chudnovsky, Jadwiga Czyżewska, Kacper Kluk, Marcin Pilipczuk, and Paweł Rzążewski. Sparse Induced Subgraphs in P₇-Free Graphs of Bounded Clique Number. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chudnovsky_et_al:LIPIcs.ISAAC.2025.20,
  author =	{Chudnovsky, Maria and Czy\.{z}ewska, Jadwiga and Kluk, Kacper and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Sparse Induced Subgraphs in P₇-Free Graphs of Bounded Clique Number}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{20:1--20:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.20},
  URN =		{urn:nbn:de:0030-drops-249282},
  doi =		{10.4230/LIPIcs.ISAAC.2025.20},
  annote =	{Keywords: P\underlinet-free graphs, maximum weight induced subgraph, maximum weight independent set}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.12
Star-Based Separators for Intersection Graphs of c-Colored Pseudo-Segments

Authors: Mark de Berg, Bart M. P. Jansen, and Jeroen S. K. Lamme

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The Planar Separator Theorem, which states that any planar graph 𝒢 has a separator consisting of O(√n) nodes whose removal partitions 𝒢 into components of size at most 2n/3, is a widely used tool to obtain fast algorithms on planar graphs. Intersection graphs of disks, which generalize planar graphs, do not admit such separators. It has recently been shown that disk graphs do admit so-called clique-based separators that consist of O(√n) cliques. This result has been generalized to intersection graphs of various other types of disk-like objects. Unfortunately, segment intersection graphs do not admit small clique-based separators, because they can contain arbitrarily large bicliques. This is true even in the simple case of axis-aligned segments. In this paper we therefore introduce biclique-based separators (and, in particular, star-based separators), which are separators consisting of a small number of bicliques (or stars). We prove that any c-oriented set of n segments in the plane, where c is a constant, admits a star-based separator consisting of O(√n) stars. In fact, our result is more general, as it applies to any set of n pseudo-segments that is partitioned into c subsets such that the pseudo-segments in the same subset are pairwise disjoint. We extend our result to intersection graphs of c-oriented polygons. These results immediately lead to an almost-exact distance oracle for such intersection graphs, which has O(n√n) storage and O(√n) query time, and that can report the hop-distance between any two query nodes in the intersection graph with an additive error of at most 2. This is the first distance oracle for such types of intersection graphs that has subquadratic storage and sublinear query time and that only has an additive error.
Cite as

Mark de Berg, Bart M. P. Jansen, and Jeroen S. K. Lamme. Star-Based Separators for Intersection Graphs of c-Colored Pseudo-Segments. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ISAAC.2025.12,
  author =	{de Berg, Mark and Jansen, Bart M. P. and Lamme, Jeroen S. K.},
  title =	{{Star-Based Separators for Intersection Graphs of c-Colored Pseudo-Segments}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.12},
  URN =		{urn:nbn:de:0030-drops-249207},
  doi =		{10.4230/LIPIcs.ISAAC.2025.12},
  annote =	{Keywords: Computational geometry, intersection graphs, biclique-based separators, distance oracles}
}
  • Refine by Type
  • 60 Document/PDF
  • 45 Document/HTML

  • Refine by Publication Year
  • 9 2026
  • 38 2025
  • 4 2024
  • 3 2023
  • 2 2022
  • Show More...

  • Refine by Author
  • 12 Le, Hung
  • 8 Solomon, Shay
  • 7 Milenković, Lazar
  • 5 Than, Cuong
  • 4 Chang, Hsien-Chih
  • Show More...

  • Refine by Series/Journal
  • 51 LIPIcs
  • 4 OASIcs
  • 1 LITES
  • 3 TGDK
  • 1 DagRep

  • Refine by Classification
  • 13 Theory of computation → Computational geometry
  • 9 Mathematics of computing → Graph algorithms
  • 7 Theory of computation → Sparsification and spanners
  • 6 Theory of computation → Design and analysis of algorithms
  • 4 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 4 Euclidean spanners
  • 3 Approximation Algorithms
  • 3 Graph Algorithms
  • 3 treewidth
  • 2 Linear Programming
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact