73 citations · 387 across the 61 of their papers we have counts for
11 papers · 1 filter
A Linear-Time Algorithm for Product Structure in Planar Graphs
Prosenjit Bose, Kaya Gouin, Pat Morin +1
The \emph{Product Structure Theorem} for planar graphs (Dujmović et al.\ \emph{JACM}, \textbf{67}(4):22) states that any planar graph is contained in the strong product of a planar…
A Fast Algorithm for the Product Structure of Planar Graphs
Pat Morin
Dujmović et al (FOCS2019) recently proved that every planar graph is a subgraph of , where denotes the strong graph product, is a graph of treewid…
Adjacency Labelling for Planar Graphs (and Beyond)
Vida Dujmović, Louis Esperet, Gwenaël Joret +3
We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an -vertex planar graph is assigned a -bit label and the lab…
Drawing Graphs as Spanners
Oswin Aichholzer, Manuel Borrazzo, Prosenjit Bose +4
We study the problem of embedding graphs in the plane as good geometric spanners. That is, for a graph , the goal is to construct a straight-line drawing of in the plane…
Encoding 3SUM
Sergio Cabello, Jean Cardinal, John Iacono +3
We consider the following problem: given three sets of real numbers, output a word-RAM data structure from which we can efficiently recover the sign of the sum of any triple of num…
Biased Predecessor Search
Prosenjit Bose, Rolf Fagerberg, John Howat +1
We consider the problem of performing predecessor searches in a bounded universe while achieving query times that depend on the distribution of queries. We obtain several data stru…
Array Layouts for Comparison-Based Searching
Paul-Virak Khuong, Pat Morin
We attempt to determine the best order and search algorithm to store comparable data items in an array, , of length so that we can, for any query value, , quickly fin…
Top-Down Skiplists
Luis Barba, Pat Morin
We describe todolists (top-down skiplists), a variant of skiplists (Pugh 1990) that can execute searches using at most binary comparisons per search…
The Fresh-Finger Property
John Howat, John Iacono, Pat Morin
The unified property roughly states that searching for an element is fast when the current access is close to a recent access. Here, "close" refers to rank distance measured among…
Notes on large angle crossing graphs
Vida Dujmovic, Joachim Gudmundsson, Pat Morin +1
A graph G is an a-angle crossing (aAC) graph if every pair of crossing edges in G intersect at an angle of at least a. The concept of right angle crossing (RAC) graphs (a=Pi/2) was…
Range Mode and Range Median Queries on Lists and Trees
Danny Krizanc, Pat Morin, Michiel Smid
We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequ…