12 Search Results for "Bhore, Sujoy"

Document
DOI: 10.4230/LIPIcs.SoCG.2023.18
Extending Orthogonal Planar Graph Drawings Is Fixed-Parameter Tractable

Authors: Sujoy Bhore, Robert Ganian, Liana Khazaliya, Fabrizio Montecchiani, and Martin Nöllenburg

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

Abstract
The task of finding an extension to a given partial drawing of a graph while adhering to constraints on the representation has been extensively studied in the literature, with well-known results providing efficient algorithms for fundamental representations such as planar and beyond-planar topological drawings. In this paper, we consider the extension problem for bend-minimal orthogonal drawings of planar graphs, which is among the most fundamental geometric graph drawing representations. While the problem was known to be NP-hard, it is natural to consider the case where only a small part of the graph is still to be drawn. Here, we establish the fixed-parameter tractability of the problem when parameterized by the size of the missing subgraph. Our algorithm is based on multiple novel ingredients which intertwine geometric and combinatorial arguments. These include the identification of a new graph representation of bend-equivalent regions for vertex placement in the plane, establishing a bound on the treewidth of this auxiliary graph, and a global point-grid that allows us to discretize the possible placement of bends and vertices into locally bounded subgrids for each of the above regions.
Cite as

Sujoy Bhore, Robert Ganian, Liana Khazaliya, Fabrizio Montecchiani, and Martin Nöllenburg. Extending Orthogonal Planar Graph Drawings Is Fixed-Parameter Tractable. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2023.18,
  author =	{Bhore, Sujoy and Ganian, Robert and Khazaliya, Liana and Montecchiani, Fabrizio and N\"{o}llenburg, Martin},
  title =	{{Extending Orthogonal Planar Graph Drawings Is Fixed-Parameter Tractable}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{18:1--18:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.18},
  URN =		{urn:nbn:de:0030-drops-178689},
  doi =		{10.4230/LIPIcs.SoCG.2023.18},
  annote =	{Keywords: orthogonal drawings, bend minimization, extension problems, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.34
Minimum Link Fencing

Authors: Sujoy Bhore, Fabian Klute, Maarten Löffler, Martin Nöllenburg, Soeren Terziadis, and Anaïs Villedieu

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We study a variant of the geometric multicut problem, where we are given a set 𝒫 of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where 𝒫 contains a polygon Q that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general and that it is XP-time solvable when each fence contains at most two polygons and the number of segments per fence is the parameter. Finally, we present an O(n log n)-time algorithm for the case that the convex hull of 𝒫⧵{Q} does not intersect Q.
Cite as

Sujoy Bhore, Fabian Klute, Maarten Löffler, Martin Nöllenburg, Soeren Terziadis, and Anaïs Villedieu. Minimum Link Fencing. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.ISAAC.2022.34,
  author =	{Bhore, Sujoy and Klute, Fabian and L\"{o}ffler, Maarten and N\"{o}llenburg, Martin and Terziadis, Soeren and Villedieu, Ana\"{i}s},
  title =	{{Minimum Link Fencing}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{34:1--34:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.34},
  URN =		{urn:nbn:de:0030-drops-173191},
  doi =		{10.4230/LIPIcs.ISAAC.2022.34},
  annote =	{Keywords: computational geometry, polygon nesting, polygon separation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.18
Online Spanners in Metric Spaces

Authors: Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh, and Csaba D. Tóth

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric t-spanner of ℳ if for every u,v ∈ X, δ(u,v) ≤ δ_G(u,v) ≤ t⋅ δ(u,v), where δ_G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s₁, …, s_n), where the points are presented one at a time (i.e., after i steps, we have seen S_i = {s₁, … , s_i}). The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. The goal is to maintain a t-spanner G_i for S_i for all i, while minimizing the number of edges, and their total weight. Under the L₂-norm in ℝ^d for arbitrary constant d ∈ ℕ, we present an online (1+ε)-spanner algorithm with competitive ratio O_d(ε^{-d} log n), improving the previous bound of O_d(ε^{-(d+1)}log n). Moreover, the spanner maintained by the algorithm has O_d(ε^{1-d}log ε^{-1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1-d})⋅ n. In the plane, a tighter analysis of the same algorithm provides an almost quadratic improvement of the competitive ratio to O(ε^{-3/2}logε^{-1}log n), by comparing the online spanner with an instance-optimal spanner directly, bypassing the comparison to an MST (i.e., lightness). As a counterpart, we design a sequence of points that yields a Ω_d(ε^{-d}) lower bound for the competitive ratio for online (1+ε)-spanner algorithms in ℝ^d under the L₁-norm. Then we turn our attention to online spanners in general metrics. Note that, it is not possible to obtain a spanner with stretch less than 3 with a subquadratic number of edges, even in the offline setting, for general metrics. We analyze an online version of the celebrated greedy spanner algorithm, dubbed ordered greedy. With stretch factor t = (2k-1)(1+ε) for k ≥ 2 and ε ∈ (0,1), we show that it maintains a spanner with O(ε^{-1}logε^{-1})⋅ n^{1+1/k} edges and O(ε^{-1}n^{1/k}log² n) lightness for a sequence of n points in a metric space. We show that these bounds cannot be significantly improved, by introducing an instance that achieves an Ω(1/k⋅ n^{1/k}) competitive ratio on both sparsity and lightness. Furthermore, we establish the trade-off among stretch, number of edges and lightness for points in ultrametrics, showing that one can maintain a (2+ε)-spanner for ultrametrics with O(ε^{-1}logε^{-1})⋅ n edges and O(ε^{-2}) lightness.
Cite as

Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh, and Csaba D. Tóth. Online Spanners in Metric Spaces. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.ESA.2022.18,
  author =	{Bhore, Sujoy and Filtser, Arnold and Khodabandeh, Hadi and T\'{o}th, Csaba D.},
  title =	{{Online Spanners in Metric Spaces}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.18},
  URN =		{urn:nbn:de:0030-drops-169564},
  doi =		{10.4230/LIPIcs.ESA.2022.18},
  annote =	{Keywords: spanner, online algorithm, lightness, sparsity, minimum weight}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.30
Hop-Spanners for Geometric Intersection Graphs

Authors: Jonathan B. Conroy and Csaba D. Tóth

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

Abstract
A t-spanner of a graph G = (V,E) is a subgraph H = (V,E') that contains a uv-path of length at most t for every uv ∈ E. It is known that every n-vertex graph admits a (2k-1)-spanner with O(n^{1+1/k}) edges for k ≥ 1. This bound is the best possible for 1 ≤ k ≤ 9 and is conjectured to be optimal due to Erdős' girth conjecture. We study t-spanners for t ∈ {2,3} for geometric intersection graphs in the plane. These spanners are also known as t-hop spanners to emphasize the use of graph-theoretic distances (as opposed to Euclidean distances between the geometric objects or their centers). We obtain the following results: (1) Every n-vertex unit disk graph (UDG) admits a 2-hop spanner with O(n) edges; improving upon the previous bound of O(nlog n). (2) The intersection graph of n axis-aligned fat rectangles admits a 2-hop spanner with O(nlog n) edges, and this bound is the best possible. (3) The intersection graph of n fat convex bodies in the plane admits a 3-hop spanner with O(nlog n) edges. (4) The intersection graph of n axis-aligned rectangles admits a 3-hop spanner with O(nlog² n) edges.
Cite as

Jonathan B. Conroy and Csaba D. Tóth. Hop-Spanners for Geometric Intersection Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{conroy_et_al:LIPIcs.SoCG.2022.30,
  author =	{Conroy, Jonathan B. and T\'{o}th, Csaba D.},
  title =	{{Hop-Spanners for Geometric Intersection Graphs}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{30:1--30:17},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.30},
  URN =		{urn:nbn:de:0030-drops-160381},
  doi =		{10.4230/LIPIcs.SoCG.2022.30},
  annote =	{Keywords: geometric intersection graph, unit disk graph, hop-spanner}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.19
Untangling Circular Drawings: Algorithms and Complexity

Authors: Sujoy Bhore, Guangping Li, Martin Nöllenburg, Ignaz Rutter, and Hsiang-Yun Wu

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We consider the problem of untangling a given (non-planar) straight-line circular drawing δ_G of an outerplanar graph G = (V,E) into a planar straight-line circular drawing by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph G, it is clear that such a crossing-free circular drawing always exists and we define the circular shifting number shift°(δ_G) as the minimum number of vertices that need to be shifted to resolve all crossings of δ_G. We show that the problem Circular Untangling, asking whether shift°(δ_G) ≤ K for a given integer K, is NP-complete. Based on this result we study Circular Untangling for almost-planar circular drawings, in which a single edge is involved in all the crossings. In this case we provide a tight upper bound shift°(δ_G) ≤ ⌊n/2⌋-1, where n is the number of vertices in G, and present a polynomial-time algorithm to compute the circular shifting number of almost-planar drawings.
Cite as

Sujoy Bhore, Guangping Li, Martin Nöllenburg, Ignaz Rutter, and Hsiang-Yun Wu. Untangling Circular Drawings: Algorithms and Complexity. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.ISAAC.2021.19,
  author =	{Bhore, Sujoy and Li, Guangping and N\"{o}llenburg, Martin and Rutter, Ignaz and Wu, Hsiang-Yun},
  title =	{{Untangling Circular Drawings: Algorithms and Complexity}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.19},
  URN =		{urn:nbn:de:0030-drops-154528},
  doi =		{10.4230/LIPIcs.ISAAC.2021.19},
  annote =	{Keywords: graph drawing, straight-line drawing, outerplanarity, NP-hardness, untangling}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.63
Space-Efficient Algorithms for Reachability in Directed Geometric Graphs

Authors: Sujoy Bhore and Rahul Jain

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
The problem of graph Reachability is to decide whether there is a path from one vertex to another in a given graph. In this paper, we study the Reachability problem on three distinct graph families - intersection graphs of Jordan regions, unit contact disk graphs (penny graphs), and chordal graphs. For each of these graph families, we present space-efficient algorithms for the Reachability problem. For intersection graphs of Jordan regions, we show how to obtain a "good" vertex separator in a space-efficient manner and use it to solve the Reachability in polynomial time and O(m^{1/2} log n) space, where n is the number of Jordan regions, and m is the total number of crossings among the regions. We use a similar approach for chordal graphs and obtain a polynomial time and O(m^{1/2} log n) space algorithm, where n and m are the number of vertices and edges, respectively. However, for unit contact disk graphs (penny graphs), we use a more involved technique and obtain a better algorithm. We show that for every ε > 0, there exists a polynomial time algorithm that can solve Reachability in an n vertex directed penny graph, using O(n^{1/4+ε}) space. We note that the method used to solve penny graphs does not extend naturally to the class of geometric intersection graphs that include arbitrary size cliques.
Cite as

Sujoy Bhore and Rahul Jain. Space-Efficient Algorithms for Reachability in Directed Geometric Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 63:1-63:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.ISAAC.2021.63,
  author =	{Bhore, Sujoy and Jain, Rahul},
  title =	{{Space-Efficient Algorithms for Reachability in Directed Geometric Graphs}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{63:1--63:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.63},
  URN =		{urn:nbn:de:0030-drops-154961},
  doi =		{10.4230/LIPIcs.ISAAC.2021.63},
  annote =	{Keywords: Reachablity, Geometric intersection graphs, Space-efficient algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.16
Online Euclidean Spanners

Authors: Sujoy Bhore and Csaba D. Tóth

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
In this paper, we study the online Euclidean spanners problem for points in ℝ^d. Given a set S of n points in ℝ^d, a t-spanner on S is a subgraph of the underlying complete graph G = (S,binom(S,2)), that preserves the pairwise Euclidean distances between points in S to within a factor of t, that is the stretch factor. Suppose we are given a sequence of n points (s₁,s₂,…, s_n) in ℝ^d, where point s_i is presented in step i for i = 1,…, n. The objective of an online algorithm is to maintain a geometric t-spanner on S_i = {s₁,…, s_i} for each step i. The algorithm is allowed to add new edges to the spanner when a new point is presented, but cannot remove any edge from the spanner. The performance of an online algorithm is measured by its competitive ratio, which is the supremum, over all sequences of points, of the ratio between the weight of the spanner constructed by the algorithm and the weight of an optimum spanner. Here the weight of a spanner is the sum of all edge weights. First, we establish a lower bound of Ω(ε^{-1}log n / log ε^{-1}) for the competitive ratio of any online (1+ε)-spanner algorithm, for a sequence of n points in 1-dimension. We show that this bound is tight, and there is an online algorithm that can maintain a (1+ε)-spanner with competitive ratio O(ε^{-1}log n / log ε^{-1}). Next, we design online algorithms for sequences of points in ℝ^d, for any constant d ≥ 2, under the L₂ norm. We show that previously known incremental algorithms achieve a competitive ratio O(ε^{-(d+1)}log n). However, if the algorithm is allowed to use additional points (Steiner points), then it is possible to substantially improve the competitive ratio in terms of ε. We describe an online Steiner (1+ε)-spanner algorithm with competitive ratio O(ε^{(1-d)/2} log n). As a counterpart, we show that the dependence on n cannot be eliminated in dimensions d ≥ 2. In particular, we prove that any online spanner algorithm for a sequence of n points in ℝ^d under the L₂ norm has competitive ratio Ω(f(n)), where lim_{n → ∞}f(n) = ∞. Finally, we provide improved lower bounds under the L₁ norm: Ω(ε^{-2}/log ε^{-1}) in the plane and Ω(ε^{-d}) in ℝ^d for d ≥ 3.
Cite as

Sujoy Bhore and Csaba D. Tóth. Online Euclidean Spanners. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.ESA.2021.16,
  author =	{Bhore, Sujoy and T\'{o}th, Csaba D.},
  title =	{{Online Euclidean Spanners}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{16:1--16:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.16},
  URN =		{urn:nbn:de:0030-drops-145974},
  doi =		{10.4230/LIPIcs.ESA.2021.16},
  annote =	{Keywords: Geometric spanner, (1+\epsilon)-spanner, minimum weight, online algorithm}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.15
Light Euclidean Steiner Spanners in the Plane

Authors: Sujoy Bhore and Csaba D. Tóth

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Lightness is a fundamental parameter for Euclidean spanners; it is the ratio of the spanner weight to the weight of the minimum spanning tree of a finite set of points in ℝ^d. In a recent breakthrough, Le and Solomon (2019) established the precise dependencies on ε > 0 and d ∈ ℕ of the minimum lightness of a (1+ε)-spanner, and observed that additional Steiner points can substantially improve the lightness. Le and Solomon (2020) constructed Steiner (1+ε)-spanners of lightness O(ε^{-1}logΔ) in the plane, where Δ ≥ Ω(√n) is the spread of the point set, defined as the ratio between the maximum and minimum distance between a pair of points. They also constructed spanners of lightness Õ(ε^{-(d+1)/2}) in dimensions d ≥ 3. Recently, Bhore and Tóth (2020) established a lower bound of Ω(ε^{-d/2}) for the lightness of Steiner (1+ε)-spanners in ℝ^d, for d ≥ 2. The central open problem in this area is to close the gap between the lower and upper bounds in all dimensions d ≥ 2. In this work, we show that for every finite set of points in the plane and every ε > 0, there exists a Euclidean Steiner (1+ε)-spanner of lightness O(ε^{-1}); this matches the lower bound for d = 2. We generalize the notion of shallow light trees, which may be of independent interest, and use directional spanners and a modified window partitioning scheme to achieve a tight weight analysis.
Cite as

Sujoy Bhore and Csaba D. Tóth. Light Euclidean Steiner Spanners in the Plane. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2021.15,
  author =	{Bhore, Sujoy and T\'{o}th, Csaba D.},
  title =	{{Light Euclidean Steiner Spanners in the Plane}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.15},
  URN =		{urn:nbn:de:0030-drops-138145},
  doi =		{10.4230/LIPIcs.SoCG.2021.15},
  annote =	{Keywords: Geometric spanner, lightness, minimum weight}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.13
On Euclidean Steiner (1+ε)-Spanners

Authors: Sujoy Bhore and Csaba D. Tóth

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
Lightness and sparsity are two natural parameters for Euclidean (1+ε)-spanners. Classical results show that, when the dimension d ∈ ℕ and ε > 0 are constant, every set S of n points in d-space admits an (1+ε)-spanners with O(n) edges and weight proportional to that of the Euclidean MST of S. Tight bounds on the dependence on ε > 0 for constant d ∈ ℕ have been established only recently. Le and Solomon (FOCS 2019) showed that Steiner points can substantially improve the lightness and sparsity of a (1+ε)-spanner. They gave upper bounds of Õ(ε^{-(d+1)/2}) for the minimum lightness in dimensions d ≥ 3, and Õ(ε^{-(d-1))/2}) for the minimum sparsity in d-space for all d ≥ 1. They obtained lower bounds only in the plane (d = 2). Le and Solomon (ESA 2020) also constructed Steiner (1+ε)-spanners of lightness O(ε^{-1}logΔ) in the plane, where Δ ∈ Ω(log n) is the spread of S, defined as the ratio between the maximum and minimum distance between a pair of points. In this work, we improve several bounds on the lightness and sparsity of Euclidean Steiner (1+ε)-spanners. Using a new geometric analysis, we establish lower bounds of Ω(ε^{-d/2}) for the lightness and Ω(ε^{-(d-1)/2}) for the sparsity of such spanners in Euclidean d-space for all d ≥ 2. We use the geometric insight from our lower bound analysis to construct Steiner (1+ε)-spanners of lightness O(ε^{-1}log n) for n points in Euclidean plane.
Cite as

Sujoy Bhore and Csaba D. Tóth. On Euclidean Steiner (1+ε)-Spanners. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.STACS.2021.13,
  author =	{Bhore, Sujoy and T\'{o}th, Csaba D.},
  title =	{{On Euclidean Steiner (1+\epsilon)-Spanners}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.13},
  URN =		{urn:nbn:de:0030-drops-136586},
  doi =		{10.4230/LIPIcs.STACS.2021.13},
  annote =	{Keywords: Geometric spanner, (1+\epsilon)-spanner, lightness, sparsity, minimum weight}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.1
Planar Bichromatic Bottleneck Spanning Trees

Authors: A. Karim Abu-Affash, Sujoy Bhore, Paz Carmi, and Joseph S. B. Mitchell

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Given a set P of n red and blue points in the plane, a planar bichromatic spanning tree of P is a geometric spanning tree of P, such that each edge connects between a red and a blue point, and no two edges intersect. In the bottleneck planar bichromatic spanning tree problem, the goal is to find a planar bichromatic spanning tree T, such that the length of the longest edge in T is minimized. In this paper, we show that this problem is NP-hard for points in general position. Our main contribution is a polynomial-time (8√2)-approximation algorithm, by showing that any bichromatic spanning tree of bottleneck λ can be converted to a planar bichromatic spanning tree of bottleneck at most 8√2 λ.
Cite as

A. Karim Abu-Affash, Sujoy Bhore, Paz Carmi, and Joseph S. B. Mitchell. Planar Bichromatic Bottleneck Spanning Trees. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{abuaffash_et_al:LIPIcs.ESA.2020.1,
  author =	{Abu-Affash, A. Karim and Bhore, Sujoy and Carmi, Paz and Mitchell, Joseph S. B.},
  title =	{{Planar Bichromatic Bottleneck Spanning Trees}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.1},
  URN =		{urn:nbn:de:0030-drops-128670},
  doi =		{10.4230/LIPIcs.ESA.2020.1},
  annote =	{Keywords: Approximation Algorithms, Bottleneck Spanning Tree, NP-Hardness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.19
An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling

Authors: Sujoy Bhore, Guangping Li, and Martin Nöllenburg

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Map labeling is a classical problem in cartography and geographic information systems (GIS) that asks to place labels for area, line, and point features, with the goal to select and place the maximum number of independent, i.e., overlap-free, labels. A practically interesting case is point labeling with axis-parallel rectangular labels of common size. In a fully dynamic setting, at each time step, either a new label appears or an existing label disappears. Then, the challenge is to maintain a maximum cardinality subset of pairwise independent labels with sub-linear update time. Motivated by this, we study the maximal independent set (MIS) and maximum independent set (Max-IS) problems on fully dynamic (insertion/deletion model) sets of axis-parallel rectangles of two types - (i) uniform height and width and (ii) uniform height and arbitrary width; both settings can be modeled as rectangle intersection graphs. We present the first deterministic algorithm for maintaining a MIS (and thus a 4-approximate Max-IS) of a dynamic set of uniform rectangles with amortized sub-logarithmic update time. This breaks the natural barrier of Ω(Δ) update time (where Δ is the maximum degree in the graph) for vertex updates presented by Assadi et al. (STOC 2018). We continue by investigating Max-IS and provide a series of deterministic dynamic approximation schemes. For uniform rectangles, we first give an algorithm that maintains a 4-approximate Max-IS with O(1) update time. In a subsequent algorithm, we establish the trade-off between approximation quality 2(1+1/k) and update time O(k²log n), for k ∈ ℕ. We conclude with an algorithm that maintains a 2-approximate Max-IS for dynamic sets of unit-height and arbitrary-width rectangles with O(ω log n) update time, where ω is the maximum size of an independent set of rectangles stabbed by any horizontal line. We have implemented our algorithms and report the results of an experimental comparison exploring the trade-off between solution quality and update time for synthetic and real-world map labeling instances.
Cite as

Sujoy Bhore, Guangping Li, and Martin Nöllenburg. An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.ESA.2020.19,
  author =	{Bhore, Sujoy and Li, Guangping and N\"{o}llenburg, Martin},
  title =	{{An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{19:1--19:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.19},
  URN =		{urn:nbn:de:0030-drops-128856},
  doi =		{10.4230/LIPIcs.ESA.2020.19},
  annote =	{Keywords: Independent Sets, Dynamic Algorithms, Rectangle Intersection Graphs, Approximation Algorithms, Experimental Evaluation}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.13
Parameterized Study of Steiner Tree on Unit Disk Graphs

Authors: Sujoy Bhore, Paz Carmi, Sudeshna Kolay, and Meirav Zehavi

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
We study the Steiner Tree problem on unit disk graphs. Given a n vertex unit disk graph G, a subset R⊆ V(G) of t vertices and a positive integer k, the objective is to decide if there exists a tree T in G that spans over all vertices of R and uses at most k vertices from V⧵ R. The vertices of R are referred to as terminals and the vertices of V(G)⧵ R as Steiner vertices. First, we show that the problem is NP-hard. Next, we prove that the Steiner Tree problem on unit disk graphs can be solved in n^{O(√{t+k})} time. We also show that the Steiner Tree problem on unit disk graphs parameterized by k has an FPT algorithm with running time 2^{O(k)}n^{O(1)}. In fact, the algorithms are designed for a more general class of graphs, called clique-grid graphs [Fomin et al., 2019]. We mention that the algorithmic results can be made to work for Steiner Tree on disk graphs with bounded aspect ratio. Finally, we prove that Steiner Tree on disk graphs parameterized by k is W[1]-hard.
Cite as

Sujoy Bhore, Paz Carmi, Sudeshna Kolay, and Meirav Zehavi. Parameterized Study of Steiner Tree on Unit Disk Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SWAT.2020.13,
  author =	{Bhore, Sujoy and Carmi, Paz and Kolay, Sudeshna and Zehavi, Meirav},
  title =	{{Parameterized Study of Steiner Tree on Unit Disk Graphs}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.13},
  URN =		{urn:nbn:de:0030-drops-122607},
  doi =		{10.4230/LIPIcs.SWAT.2020.13},
  annote =	{Keywords: Unit Disk Graphs, FPT, Subexponential exact algorithms, NP-Hardness, W-Hardness}
}
  • Refine by Author
  • 11 Bhore, Sujoy
  • 5 Tóth, Csaba D.
  • 4 Nöllenburg, Martin
  • 2 Carmi, Paz
  • 2 Li, Guangping
  • Show More...

  • Refine by Classification
  • 11 Theory of computation → Computational geometry
  • 5 Mathematics of computing → Paths and connectivity problems
  • 4 Mathematics of computing → Approximation algorithms
  • 1 Human-centered computing → Graph drawings
  • 1 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 4 minimum weight
  • 3 Geometric spanner
  • 3 lightness
  • 2 (1+ε)-spanner
  • 2 Approximation Algorithms
  • Show More...

  • Refine by Type
  • 12 document

  • Refine by Publication Year
  • 5 2021
  • 3 2020
  • 3 2022
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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