Prosenjit Bose
YOU?
Author Swipe
View article: On k-planar Graphs without Short Cycles
On k-planar Graphs without Short Cycles Open
We study the impact of forbidding short cycles to the edge density of k-planar graphs; a k-planar graph is one that can be drawn in the plane with at most k crossings per edge. Specifically, we consider three settings, according to which t…
View article: Computing Shortest Paths Amid Non-overlapping Weighted Disks
Computing Shortest Paths Amid Non-overlapping Weighted Disks Open
In this article, we present an approximation algorithm for solving the Weighted Region Problem amidst a set of n non-overlapping weighted disks in the plane. For a given parameter $$ \varepsilon \in (0,1]$$ , the length of the app…
View article: An Improved Bound for Plane Covering Paths
An Improved Bound for Plane Covering Paths Open
A covering path for a finite set $P$ of points in the plane is a polygonal path such that every point of $P$ lies on a segment of the path. The vertices of the path need not be at points of $P$. A covering path is plane if its segments do …
View article: Tight Routing and Spanning Ratios of Arbitrary Triangle Delaunay Graphs
Tight Routing and Spanning Ratios of Arbitrary Triangle Delaunay Graphs Open
A Delaunay graph built on a planar point set has an edge between two vertices when there exists a disk with the two vertices on its boundary and no vertices in its interior. When the disk is replaced with an equilateral triangle, the resul…
View article: On Separating Path and Tree Systems in Graphs
On Separating Path and Tree Systems in Graphs Open
We explore the concept of separating systems of vertex sets of graphs. A separating system of a set $X$ is a collection of subsets of $X$ such that for any pair of distinct elements in $X$, there exists a set in the separating system that …
View article: On 1-planar graphs with bounded cop-number
On 1-planar graphs with bounded cop-number Open
View article: Computational aspects of disks enclosing many points
Computational aspects of disks enclosing many points Open
View article: The basis number of 1-planar graphs
The basis number of 1-planar graphs Open
Let $B$ be a set of Eulerian subgraphs of a graph $G$. We say $B$ forms a $k$-basis if it is a minimum set that generates the cycle space of $G$, and any edge of $G$ lies in at most $k$ members of $B$. The basis number of a graph $G$, deno…
View article: On the $d$-independence number in 1-planar graphs
On the $d$-independence number in 1-planar graphs Open
The $d$-independence number of a graph $G$ is the largest possible size of an independent set $I$ in $G$ where each vertex of $I$ has degree at least $d$ in $G$. Upper bounds for the $d$-independence number in planar graphs are well-known …
View article: Noncrossing Longest Paths and Cycles
Noncrossing Longest Paths and Cycles Open
Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short geometric structures such as shortest perfect matchings, s…
View article: On 1-Planar Graphs with Bounded Cop-Number
On 1-Planar Graphs with Bounded Cop-Number Open
Cops and Robbers is a type of pursuit-evasion game played on a graph where a set of cops try to capture a single robber. The cops first choose their initial vertex positions, and later the robber chooses a vertex. The cops and robbers make…
View article: Computing shortest paths amid non-overlapping weighted disks
Computing shortest paths amid non-overlapping weighted disks Open
In this article, we present an approximation algorithm for solving the Weighted Region Problem amidst a set of $ n $ non-overlapping weighted disks in the plane. For a given parameter $ \varepsilon \in (0,1]$, the length of the approximate…
View article: On $k$-planar Graphs without Short Cycles
On $k$-planar Graphs without Short Cycles Open
We study the impact of forbidding short cycles to the edge density of $k$-planar graphs; a $k$-planar graph is one that can be drawn in the plane with at most $k$ crossings per edge. Specifically, we consider three settings, according to w…
View article: Routing on heavy path WSPD spanners
Routing on heavy path WSPD spanners Open
In this article, we present a construction of a spanner on a set of n points in Rd that we call a heavy path WSPD spanner. The construction is parameterized by a constant s>2 called the separation ratio. The size of the graph is O(sdn) and…
View article: Computing Vertex and Edge Connectivity of Graphs Embedded with Crossings
Computing Vertex and Edge Connectivity of Graphs Embedded with Crossings Open
Vertex connectivity and edge connectivity are fundamental concepts in graph theory that have been widely studied from both structural and algorithmic perspectives. The focus of this paper is on computing these two parameters for graphs emb…
View article: A Steiner-point-based algorithm for approximate shortest paths in weighted equilateral-triangle meshes
A Steiner-point-based algorithm for approximate shortest paths in weighted equilateral-triangle meshes Open
Let T be a tessellation composed of equilateral triangular regions, where each region has an associated positive weight. We present two methods that discretize the space based on the placement of Steiner points in the cells of T. Using suc…
View article: Approximating shortest paths in weighted square and hexagonal meshes
Approximating shortest paths in weighted square and hexagonal meshes Open
Continuous 2-dimensional space is often discretized by considering a mesh of weighted cells. In this work we study how well a weighted mesh approximates the space, with respect to shortest paths. We consider a shortest path $ \mathit{SP_w}…
View article: Approximating the Smallest $k$-Enclosing Geodesic Disc in a Simple Polygon
Approximating the Smallest $k$-Enclosing Geodesic Disc in a Simple Polygon Open
We consider the problem of finding a geodesic disc of smallest radius containing at least $k$ points from a set of $n$ points in a simple polygon that has $m$ vertices, $r$ of which are reflex vertices. We refer to such a disc as a SKEG di…
View article: On 1-Planar Graphs with Bounded Cop-Number
On 1-Planar Graphs with Bounded Cop-Number Open
View article: Routing on Heavy Path WSPD Spanners
Routing on Heavy Path WSPD Spanners Open
In this article, we present a construction of a spanner on a set of $n$ points in $\mathbf{R}^d$ that we call a heavy path WSPD spanner. The construction is parameterized by a constant $s > 2$ called the separation ratio. The size of the g…
View article: The Exact Spanning Ratio of the Parallelogram Delaunay Graph
The Exact Spanning Ratio of the Parallelogram Delaunay Graph Open
Finding the exact spanning ratio of a Delaunay graph has been one of the longstanding open problems in Computational Geometry. Currently there are only four convex shapes for which the exact spanning ratio of their Delaunay graph is known:…
View article: On Separating Path and Tree Systems in Graphs
On Separating Path and Tree Systems in Graphs Open
We explore the concept of separating systems of vertex sets of graphs. A separating system of a set $X$ is a collection of subsets of $X$ such that for any pair of distinct elements in $X$, there exists a set in the separating system that …
View article: Connected Dominating Sets in Triangulations
Connected Dominating Sets in Triangulations Open
We show that every $n$-vertex triangulation has a connected dominating set of size at most $10n/21$. Equivalently, every $n$ vertex triangulation has a spanning tree with at least $11n/21$ leaves. Prior to the current work, the best known …
View article: Competitive Online Search Trees on Trees
Competitive Online Search Trees on Trees Open
We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of …
View article: On approximating shortest paths in weighted triangular tessellations
On approximating shortest paths in weighted triangular tessellations Open
We study the quality of weighted shortest paths when a continuous 2-dimensional space is discretized by a weighted triangular tessellation. In order to evaluate how well the tessellation approximates the 2-dimensional space, we study three…
View article: The Minimum Moving Spanning Tree Problem
The Minimum Moving Spanning Tree Problem Open
We investigate the problem of finding a spanning tree of a set of $n$ moving points in $\mathbb{R}^{\dim}$ that minimizes the maximum total weight (under any convex distance function) or the maximum bottleneck throughout the motion. The ou…
View article: Fragile complexity of adaptive algorithms
Fragile complexity of adaptive algorithms Open
The fragile complexity of a comparison-based algorithm is $f(n)$ if each input
element participates in $O(f(n))$ comparisons.
In this paper, we explore the fragile complexity of algorithms adaptive to
various restrictions on th…
element participates in $O(f(n))$ comparisons.
In this paper, we explore the fragile complexity of algorithms adaptive to
various restrictions on th…
View article: Linear versus centred chromatic numbers
Linear versus centred chromatic numbers Open
$\DeclareMathOperator{\chicen}{χ_{\mathrm{cen}}}\DeclareMathOperator{\chilin}{χ_{\mathrm{lin}}}$ A centred colouring of a graph is a vertex colouring in which every connected subgraph contains a vertex whose colour is unique and a \emph{li…
View article: Separating layered treewidth and row treewidth
Separating layered treewidth and row treewidth Open
Layered treewidth and row treewidth are recently introduced graph parameters that have been key ingredients in the solution of several well-known open problems. It follows from the definitions that the layered treewidth of a graph is at mo…
View article: Optimal Algorithms for Separating a Polyhedron from its Single-Part Mold
Optimal Algorithms for Separating a Polyhedron from its Single-Part Mold Open
Casting is a manufacturing process where liquid material is poured into a mold having the shape of a desired product. After the material solidifies, the product is removed from the mold. We study the case where the mold is made of a single…