73 citations · 387 across the 61 of their papers we have counts for
27 papers · 1 filter
Min--planar Drawings of Graphs
Carla Binucci, Aaron Büngener, Giuseppe Di Battista +7
The study of nonplanar drawings of graphs with restricted crossing configurations is a well-established topic in graph drawing, often referred to as beyond-planar graph drawing. On…
Near-Optimal -Robust Geometric Spanners
Prosenjit Bose, Paz Carmi, Vida Dujmovic +1
For any constants , , , and any -point set , we show that there is a geometric graph having edges with…
Stabbing Pairwise Intersecting Disks by Four Points
Paz Carmi, Matthew J. Katz, Pat Morin
In their seminal work, Danzer (1956, 1986) and Stachó (1981) established that every set of pairwise intersecting disks in the plane can be stabbed by four points. However, both the…
Geodesic Obstacle Representation of Graphs
Prosenjit Bose, Paz Carmi, Vida Dujmovic +4
An obstacle representation of a graph is a mapping of the vertices onto points in the plane and a set of connected regions of the plane (called obstacles) such that the straight-li…
EPG-representations with small grid-size
Therese Biedl, Martin Derka, Vida Dujmovic +1
In an EPG-representation of a graph each vertex is represented by a path in the rectangular grid, and is an edge in if and only if the paths representing an …
Spanning Trees in Multipartite Geometric Graphs
Ahmad Biniaz, Prosenjit Bose, David Eppstein +3
Let and be two disjoint sets of points in the plane where the points of are colored red and the points of are colored blue, and let . A bichromatic spa…
The Price of Order
Prosenjit Bose, Pat Morin, André van Renssen
We present tight bounds on the spanning ratio of a large family of ordered -graphs. A -graph partitions the plane around each vertex into disjoint cones, each having aper…
Compatible Connectivity-Augmentation of Planar Disconnected Graphs
Greg Aloupis, Luis Barba, Paz Carmi +3
Motivated by applications to graph morphing, we consider the following \emph{compatible connectivity-augmentation problem}: We are given a labelled -vertex planar graph, $\mathc…
Towards Tight Bounds on Theta-Graphs
Prosenjit Bose, Jean-Lou De Carufel, Pat Morin +2
We present improved upper and lower bounds on the spanning ratio of -graphs with at least six cones. Given a set of points in the plane, a -graph partitions the plane around…
Average Stretch Factor: How Low Does It Go?
Vida Dujmovic, Pat Morin, Michiel Smid
In a geometric graph, , the \emph{stretch factor} between two vertices, and , is the ratio between the Euclidean length of the shortest path from to in and th…
On the Average Number of Edges in Theta Graphs
Pat Morin, Sander Verdonschot
Theta graphs are important geometric graphs that have many applications, including wireless networking, motion planning, real-time animation, and minimum-spanning tree construction…
Visibility-Monotonic Polygon Deflation
Prosenjit Bose, Vida Dujmović, Nima Hoda +1
A deflated polygon is a polygon with no visibility crossings. We answer a question posed by Devadoss et al. (2012) by presenting a polygon that cannot be deformed via continuous vi…
Approximating Majority Depth
Dan Chen, Pat Morin
We consider the problem of approximating the majority depth (Liu and Singh, 1993) of a point q with respect to an n-point set, S, by random sampling. At the heart of this problem i…
Robust Geometric Spanners
Prosenjit Bose, Vida Dujmovic, Pat Morin +1
Highly connected and yet sparse graphs (such as expanders or graphs of high treewidth) are fundamental, widely applicable and extensively studied combinatorial objects. We initiate…
A Note on Interference in Random Point Sets
Luc Devroye, Pat Morin
The (maximum receiver-centric) interference of a geometric graph (von Rickenbach etal (2005)) is studied. It is shown that, with high probability, the following results hold for a…
A Tight Bound on the Maximum Interference of Random Sensors in the Highway Model
Evangelos Kranakis, Danny Krizanc, Pat Morin +2
Consider sensors whose positions are represented by uniform, independent and identically distributed random variables assuming values in the open unit interval . A n…
Odds-On Trees
Prosenjit Bose, Luc Devroye, Karim Douieb +3
Let R^d -> A be a query problem over R^d for which there exists a data structure S that can compute P(q) in O(log n) time for any query point q in R^d. Let D be a probability measu…
Point Location in Disconnected Planar Subdivisions
Prosenjit Bose, Luc Devroye, Karim Douieb +3
Let be a (possibly disconnected) planar subdivision and let be a probability measure over . The current paper shows how to preprocess into an O(n) size data s…
Planar Visibility: Testing and Counting
Joachim Gudmundsson, Pat Morin
In this paper we consider query versions of visibility testing and visibility counting. Let be a set of disjoint line segments in and let be an element of . V…
Memoryless Routing in Convex Subdivisions: Random Walks are Optimal
Dan Chen, Luc Devroye, Vida Dujmovic +1
A memoryless routing algorithm is one in which the decision about the next edge on the route to a vertex t for a packet currently located at vertex v is made based only on the coor…
On the Expected Maximum Degree of Gabriel and Yao Graphs
Luc Devroye, Joachim Gudmundsson, Pat Morin
Motivated by applications of Gabriel graphs and Yao graphs in wireless ad-hoc networks, we show that the maximal degree of a random Gabriel graph or Yao graph defined on points…
Algorithms for Marketing-Mix Optimization
Joachim Gudmundsson, Pat Morin, Michiel Smid
Algorithms for determining quality/cost/price tradeoffs in saturated markets are considered. A product is modeled by real-valued qualities whose sum determines the unit cost of…
Entropy, Triangulation, and Point Location in Planar Subdivisions
Sebastien Collette, Vida Dujmovic, John Iacono +2
A data structure is presented for point location in connected planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query tim…
Biased Range Trees
Vida Dujmovic, John Howat, Pat Morin
A data structure, called a biased range tree, is presented that preprocesses a set S of n points in R^2 and a query distribution D for 2-sided orthogonal range counting queries. Th…