15 papers
On the Spanning Ratio of the Greedy Triangulation for Convex Point Sets
Prosenjit Bose, Jean Lou de Carufel, Anil Maheshwari +3
The greedy triangulation of a finite planar point set is obtained by considering all segments in nondecreasing order of length and inserting each segment that does not cross an ear…
3-packings in Triangulations: Algorithms, bounds, and Complexity
Prosenjit Bose, Anil Maheshwari, Bobby Miraftab +1
We study -packings in plane triangulations for the three-vertex graphs . For a graph , let denote the maximum size of an -packing in…
Cops and robber in graphs with bounded vertex cover number
Prosenjit Bose, Louis Esperet, Jędrzej Hodor +3
Meyniel's conjecture states that -vertex connected graphs have cop number . The current best known upper bound is , proved independentl…
Computational aspects of disks enclosing many points
Prosenjit Bose, Guillermo Esteban, Tyler Tuttle
Let be a set of points in the plane. We present several different algorithms for finding a pair of points in such that any disk that contains that pair must contain at…
An Improved Bound for Plane Covering Paths
Hugo A. Akitaya, Greg Aloupis, Ahmad Biniaz +8
A covering path for a finite set of points in the plane is a polygonal path such that every point of lies on a segment of the path. The vertices of the path need not be at…
Tight Routing and Spanning Ratios of Arbitrary Triangle Delaunay Graphs
Prosenjit Bose, Jean-Lou De Carufel, John Stuart
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 t…
On geodesic disks enclosing many points
Prosenjit Bose, Guillermo Esteban, David Orden +2
Let be the largest number such that for every set of points in a polygon~, there always exist two points , where every geodesic disk contain…
Closest Pair Queries in Vertical Slabs and Tight Bounds on the Number of Possible Answers
Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung +6
Let be a set of points in , where is a constant, and let be a sequence of vertical hyperplanes that are sorted by their fi…
The basis number of 1-planar graphs
Saman Bazargani, Therese Biedl, Prosenjit Bose +2
Let be a set of Eulerian subgraphs of a graph . We say forms a -basis if it is a minimum set that generates the cycle space of , and any edge of lies in at mos…
On the -independence number in 1-planar graphs
Therese Biedl, Prosenjit Bose, Babak Miraftab
The -independence number of a graph is the largest possible size of an independent set in where each vertex of has degree at least in . Upper bounds for t…
Noncrossing Longest Paths and Cycles
Greg Aloupis, Ahmad Biniaz, Prosenjit Bose +7
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…
On 1-Planar Graphs with Bounded Cop-Number
Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari +1
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 l…
Computing shortest paths amid non-overlapping weighted disks
Prosenjit Bose, Jean-Lou De Carufel, Guillermo Esteban +1
In this article, we present an approximation algorithm for solving the Weighted Region Problem amidst a set of non-overlapping weighted disks in the plane. For a given parame…
Computing Vertex and Edge Connectivity of Graphs Embedded with Crossings
Therese Biedl, Prosenjit Bose, Karthik Murali
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 thi…
Approximating shortest paths in weighted square and hexagonal meshes
Prosenjit Bose, Guillermo Esteban, David Orden +1
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…