Prosenjit Bose

research

∙ 05/30/2022

Linear versus centred chromatic numbers

We prove that the linear chromatic number of any k× k pseudogrid is Ω(k)...

Prosenjit Bose, et al. ∙

research

∙ 04/25/2022

Pursuit-Evasion in Graphs: Zombies, Lazy Zombies and a Survivor

We study zombies and survivor, a variant of the game of cops and robber ...

Prosenjit Bose, et al. ∙

research

∙ 02/17/2022

An Optimal Algorithm for Product Structure in Planar Graphs

The Product Structure Theorem for planar graphs (Dujmović et al.JACM, 67...

Prosenjit Bose, et al. ∙

research

∙ 11/27/2021

On approximating shortest paths in weighted triangular tessellations

We study the quality of weighted shortest paths when a continuous 2-dime...

Prosenjit Bose, et al. ∙

research

∙ 06/28/2021

Dynamic Schnyder Woods

A realizer, commonly known as Schnyder woods, of a triangulation is a pa...

Sujoy Bhore, et al. ∙

research

∙ 06/02/2021

Improved Spanning on Theta-5

We show an upper bound of sin(3π/10) /sin(2π/5)-sin(3π/10) <5.70 ...

Prosenjit Bose, et al. ∙

research

∙ 05/04/2021

Separating layered treewidth and row treewidth

Layered treewidth and row treewidth are recently introduced graph parame...

Prosenjit Bose, et al. ∙

research

∙ 01/30/2021

Fragile Complexity of Adaptive Algorithms

The fragile complexity of a comparison-based algorithm is f(n) if each i...

Prosenjit Bose, et al. ∙

research

∙ 11/04/2020

Affine invariant triangulations

We study affine invariant 2D triangulation methods. That is, methods tha...

Prosenjit Bose, et al. ∙

research

∙ 07/13/2020

Asymptotically Optimal Vertex Ranking of Planar Graphs

A (vertex) ℓ-ranking is a labelling φ:V(G)→ℕ of the vertices of a graph ...

Prosenjit Bose, et al. ∙

research

∙ 02/22/2020

(Faster) Multi-Sided Boundary Labelling

A 1-bend boundary labelling problem consists of an axis-aligned rectangl...

Prosenjit Bose, et al. ∙

research

∙ 02/13/2020

Drawing Graphs as Spanners

We study the problem of embedding graphs in the plane as good geometric ...

Oswin Aichholzer, et al. ∙

research

∙ 02/12/2020

Parameterized Complexity of Two-Interval Pattern Problem

A 2-interval is the union of two disjoint intervals on the real line. Tw...

Prosenjit Bose, et al. ∙

research

∙ 10/31/2019

Expected Complexity of Routing in Θ 6 and Half-Θ 6 Graphs

We study online routing algorithms on the Θ6-graph and the half-Θ6-graph...

Prosenjit Bose, et al. ∙

research

∙ 08/02/2019

Competitive Online Search Trees on Trees

We consider the design of adaptive data structures for searching element...

Prosenjit Bose, et al. ∙

research

∙ 03/17/2019

Computing Maximum Independent Set on Outerstring Graphs and Their Relatives

A graph G with n vertices is called an outerstring graph if it has an in...

Prosenjit Bose, et al. ∙

research

∙ 12/24/2018

Near-Optimal O(k)-Robust Geometric Spanners

For any constants d> 1, ϵ >0, t>1, and any n-point set P⊂R^d, we show th...

Prosenjit Bose, et al. ∙

research

∙ 12/17/2018

Stabbing Pairwise Intersecting Disks by Four Points

Following the seminal works of Danzer (1956, 1986) and Stachó (1965,1981...

Ahmad Biniaz, et al. ∙

research

∙ 09/26/2018

Gathering by Repulsion

We consider a repulsion actuator located in an n-sided convex environmen...

Prosenjit Bose, et al. ∙

research

∙ 08/31/2018

Pole Dancing: 3D Morphs for Tree Drawings

We study the question whether a crossing-free 3D morph between two strai...

Elena Arseneva, et al. ∙

research

∙ 08/03/2018

On the Spanning and Routing Ratio of Theta-Four

We present a routing algorithm for the Theta-4-graph that computes a pat...

Prosenjit Bose, et al. ∙

research

∙ 04/19/2018

Improved Bounds for Guarding Plane Graphs with Edges

An "edge guard set" of a plane graph G is a subset Γ of edges of G such ...

Ahmad Biniaz, et al. ∙

research

∙ 03/28/2018

Boundary Labeling for Rectangular Diagrams

Given a set of n points (sites) inside a rectangle R and n points (label...

Prosenjit Bose, et al. ∙

research

∙ 03/09/2018

Geodesic Obstacle Representation of Graphs

An obstacle representation of a graph is a mapping of the vertices onto ...

Prosenjit Bose, et al. ∙

research

∙ 03/08/2018

Routing on the Visibility Graph

We consider the problem of routing on a network in the presence of line ...

Prosenjit Bose, et al. ∙

research

∙ 02/26/2018

Faster Algorithms for some Optimization Problems on Collinear Points

We propose faster algorithms for the following three optimization proble...

Ahmad Biniaz, et al. ∙

research

∙ 01/07/2018

Reconstructing a convex polygon from its ω-cloud

An ω-wedge is the (closed) set of all points contained between two rays ...

Prosenjit Bose, et al. ∙

research

∙ 10/23/2017

Constrained Routing Between Non-Visible Vertices

In this paper we study local routing strategies on geometric graphs. Suc...

Prosenjit Bose, et al. ∙

research

∙ 08/14/2017

On the Separation of a Polyhedron from Its Single-Part Mold

Casting is a manufacturing process where liquid material is poured into ...

Prosenjit Bose, et al. ∙

research

∙ 06/25/2017

Optimal Art Gallery Localization is NP-hard

Art Gallery Localization (AGL) is the problem of placing a set T of broa...

Prosenjit Bose, et al. ∙

research

∙ 06/21/2017

Art Gallery Localization

We study the problem of placing a set T of broadcast towers in a simple ...

Prosenjit Bose, et al. ∙

research

∙ 07/09/2015

The Shadows of a Cycle Cannot All Be Paths

A "shadow" of a subset S of Euclidean space is an orthogonal projection ...

Prosenjit Bose, et al. ∙

research

∙ 05/01/2008

Morphing of Triangular Meshes in Shape Space

We present a novel approach to morph between two isometric poses of the ...

Stefanie Wuhrer, et al. ∙

Prosenjit Bose

Featured Co-authors