
Dynamic Schnyder Woods
A realizer, commonly known as Schnyder woods, of a triangulation is a pa...
read it

Improved Spanning on Theta5
We show an upper bound of sin(3π/10) /sin(2π/5)sin(3π/10) <5.70 ...
read it

Separating layered treewidth and row treewidth
Layered treewidth and row treewidth are recently introduced graph parame...
read it

Fragile Complexity of Adaptive Algorithms
The fragile complexity of a comparisonbased algorithm is f(n) if each i...
read it

Affine invariant triangulations
We study affine invariant 2D triangulation methods. That is, methods tha...
read it

Asymptotically Optimal Vertex Ranking of Planar Graphs
A (vertex) ℓranking is a labelling φ:V(G)→ℕ of the vertices of a graph ...
read it

(Faster) MultiSided Boundary Labelling
A 1bend boundary labelling problem consists of an axisaligned rectangl...
read it

Drawing Graphs as Spanners
We study the problem of embedding graphs in the plane as good geometric ...
read it

Parameterized Complexity of TwoInterval Pattern Problem
A 2interval is the union of two disjoint intervals on the real line. Tw...
read it

Expected Complexity of Routing in Θ 6 and HalfΘ 6 Graphs
We study online routing algorithms on the Θ6graph and the halfΘ6graph...
read it

Competitive Online Search Trees on Trees
We consider the design of adaptive data structures for searching element...
read it

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...
read it

NearOptimal O(k)Robust Geometric Spanners
For any constants d> 1, ϵ >0, t>1, and any npoint set P⊂R^d, we show th...
read it

Stabbing Pairwise Intersecting Disks by Four Points
Following the seminal works of Danzer (1956, 1986) and Stachó (1965,1981...
read it

Gathering by Repulsion
We consider a repulsion actuator located in an nsided convex environmen...
read it

Pole Dancing: 3D Morphs for Tree Drawings
We study the question whether a crossingfree 3D morph between two strai...
read it

On the Spanning and Routing Ratio of ThetaFour
We present a routing algorithm for the Theta4graph that computes a pat...
read it

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 ...
read it

Boundary Labeling for Rectangular Diagrams
Given a set of n points (sites) inside a rectangle R and n points (label...
read it

Geodesic Obstacle Representation of Graphs
An obstacle representation of a graph is a mapping of the vertices onto ...
read it

Routing on the Visibility Graph
We consider the problem of routing on a network in the presence of line ...
read it

Faster Algorithms for some Optimization Problems on Collinear Points
We propose faster algorithms for the following three optimization proble...
read it

Reconstructing a convex polygon from its ωcloud
An ωwedge is the (closed) set of all points contained between two rays ...
read it

Constrained Routing Between NonVisible Vertices
In this paper we study local routing strategies on geometric graphs. Suc...
read it

On the Separation of a Polyhedron from Its SinglePart Mold
Casting is a manufacturing process where liquid material is poured into ...
read it

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

Art Gallery Localization
We study the problem of placing a set T of broadcast towers in a simple ...
read it

The Shadows of a Cycle Cannot All Be Paths
A "shadow" of a subset S of Euclidean space is an orthogonal projection ...
read it

Morphing of Triangular Meshes in Shape Space
We present a novel approach to morph between two isometric poses of the ...
read it
Prosenjit Bose
is this you? claim profile
Professor (Computer Science) and Associate Dean Research (Faculty of Science) at Carleton University since 1997