Prosenjit Bose

activity

20232025

collaborators

5 papers

cs.DM2025

Cops and Robbers for Graphs on Surfaces with Crossings

Prosenjit Bose, Pat Morin, Karthik Murali

Cops and Robbers is a game played on a graph where a set of cops attempt to capture a single robber. The game proceeds in rounds, where each round first consists of the cops' turn,…

math.CO2024

On $k$ -planar Graphs without Short Cycles

Michael A. Bekos, Prosenjit Bose, Aaron Büngener +6

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

cs.CG2024

Approximating the Smallest $k$ -Enclosing Geodesic Disc in a Simple Polygon

Prosenjit Bose, Anthony D'Angelo, Stephane Durocher

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

cs.CG2023

Routing on Heavy Path WSPD Spanners

Prosenjit Bose, Tyler Tuttle

In this article, we present a construction of a spanner on a set of $n$ points in $R^{d}$ that we call a heavy path WSPD spanner. The construction is parameterized by a cons…

math.CO2023

Connected Dominating Sets in Triangulations

Prosenjit Bose, Vida Dujmović, Hussein Houdrouge +2

We show that every $n$ -vertex triangulation has a connected dominating set of size at most $10 n /21$ . Equivalently, every $n$ vertex triangulation has a spanning tree with at least…

Cops and Robbers for Graphs on Surfaces with Crossings

On k-planar Graphs without Short Cycles

Approximating the Smallest k-Enclosing Geodesic Disc in a Simple Polygon

Routing on Heavy Path WSPD Spanners

Connected Dominating Sets in Triangulations

On $k$ -planar Graphs without Short Cycles

Approximating the Smallest $k$ -Enclosing Geodesic Disc in a Simple Polygon