Pat Morin

According to our database1, Pat Morin authored at least 144 papers between 1997 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.



In proceedings 
PhD thesis 





Planar Graphs Have Bounded Queue-Number.
J. ACM, 2020

Asymptotically Optimal Vertex Ranking of Planar Graphs.
CoRR, 2020

Two Results on Layered Pathwidth and Linear Layouts.
CoRR, 2020

A Fast Algorithm for the Product Structure of Planar Graphs.
CoRR, 2020

Adjacency Labelling for Planar Graphs (and Beyond).
CoRR, 2020

Drawing Graphs as Spanners.
CoRR, 2020

Notes on growing a tree in a graph.
Random Struct. Algorithms, 2019

The structure of k-planar graphs.
CoRR, 2019

Encoding 3SUM.
CoRR, 2019

Queue Layouts of Graphs with Bounded Degree and Bounded Genus.
CoRR, 2019

More Turán-Type Theorems for Triangles in Convex Point Sets.
Electron. J. Comb., 2019

Every Collinear Set in a Planar Graph Is Free.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Dual Circumference and Collinear Sets.
Proceedings of the 35th International Symposium on Computational Geometry, 2019

Corrigendum: Orthogonal Tree Decompositions of Graphs.
SIAM J. Discret. Math., 2018

Orthogonal Tree Decompositions of Graphs.
SIAM J. Discret. Math., 2018

Near-Optimal O(k)-Robust Geometric Spanners.
CoRR, 2018

Stabbing Pairwise Intersecting Disks by Four Points.
CoRR, 2018

Minor-closed graph classes with bounded layered pathwidth.
CoRR, 2018

A note on interference in random networks.
Comput. Geom., 2018

Spanning Trees in Multipartite Geometric Graphs.
Algorithmica, 2018

Anagram-Free Chromatic Number Is Not Pathwidth-Bounded.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2018

Geodesic Obstacle Representation of Graphs.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs.
Proceedings of the 34th International Symposium on Computational Geometry, 2018

Array Layouts for Comparison-Based Searching.
ACM J. Exp. Algorithmics, 2017

Layered separators in minor-closed graph classes with applications.
J. Comb. Theory, Ser. B, 2017

New Bounds for Facial Nonrepetitive Colouring.
Graphs Comb., 2017

Encoding Arguments.
ACM Comput. Surv., 2017

EPG-representations with Small Grid-Size.
Proceedings of the Graph Drawing and Network Visualization - 25th International Symposium, 2017

Towards tight bounds on theta-graphs: More is not always better.
Theor. Comput. Sci., 2016

The Price of Order.
Int. J. Comput. Geom. Appl., 2016

Biased Predecessor Search.
Algorithmica, 2016

Average Stretch Factor: How Low Does It Go?
Discret. Comput. Geom., 2015

Compatible Connectivity Augmentation of Planar Disconnected Graphs.
Discret. Comput. Geom., 2015

Reprint of: Approximating majority depth.
Comput. Geom., 2015

The θ<sub>5</sub>-graph is a spanner.
Comput. Geom., 2015

On Obstacle Numbers.
Electron. J. Comb., 2015

Visibility-monotonic polygon deflation.
Contributions Discret. Math., 2015

Towards Tight Bounds on Theta-Graphs.
CoRR, 2014

Top-Down Skiplists.
CoRR, 2014

Guest Editor's Introduction.
Comput. Geom., 2014

Crossings in Grid Drawings.
Electron. J. Comb., 2014

Searching by Panning and Zooming.
Proceedings of the 26th Canadian Conference on Computational Geometry, 2014

On the Average Number of Edges in Theta Graphs.
Proceedings of the 2014 Proceedings of the Eleventh Workshop on Analytic Algorithmics and Combinatorics, 2014

Robust Geometric Spanners.
SIAM J. Comput., 2013

Coverage with k-transmitters in the presence of obstacles.
J. Comb. Optim., 2013

The Fresh-Finger Property
CoRR, 2013

Layered Separators in Minor-Closed Families with Applications.
CoRR, 2013

Absolute approximation of Tukey depth: Theory and experiments.
Comput. Geom., 2013

Approximating majority depth.
Comput. Geom., 2013

Oja centers and centers of gravity.
Comput. Geom., 2013

Fast local searches and updates in bounded universes.
Comput. Geom., 2013

The θ 5-Graph is a Spanner.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2013

Layered Separators for Queue Layouts, 3D Graph Drawing and Nonrepetitive Coloring.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

A History of Distribution-Sensitive Data Structures.
Proceedings of the Space-Efficient Data Structures, 2013

Entropy, triangulation, and point location in planar subdivisions.
ACM Trans. Algorithms, 2012

Succinct geometric indexes supporting point location queries.
ACM Trans. Algorithms, 2012

A distribution-sensitive dictionary with low space overhead.
J. Discrete Algorithms, 2012

Skip lift: A probabilistic alternative to red-black trees.
J. Discrete Algorithms, 2012

Ghost chimneys.
Int. J. Comput. Geom. Appl., 2012

The theta-5-graph is a spanner
CoRR, 2012

A Note on Interference in Random Point Sets
CoRR, 2012

Memoryless routing in convex subdivisions: Random walks are optimal.
Comput. Geom., 2012

Biased Range Trees.
Algorithmica, 2012

Optimal Bounds on Theta-Graphs: More is not Always Better.
Proceedings of the 24th Canadian Conference on Computational Geometry, 2012

Randomized rendezvous with limited memory.
ACM Trans. Algorithms, 2011

Notes on Large Angle Crossing Graphs.
Chic. J. Theor. Comput. Sci., 2011

Algorithms for Marketing-Mix Optimization.
Algorithmica, 2011

Preprocessing Imprecise Points for Delaunay Triangulation: Simplified and Extended.
Algorithmica, 2011

Algorithms for Bivariate Majority Depth.
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

Sigma-local graphs.
J. Discrete Algorithms, 2010

A Tight Bound on the Maximum Interference of Random Sensors in the Highway Model
CoRR, 2010

Odds-On Trees
CoRR, 2010

Point Location in Disconnected Planar Subdivisions
CoRR, 2010

Improved Methods For Generating Quasi-gray Codes.
Proceedings of the Algorithm Theory, 2010

Planar visibility: testing and counting.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

Coverage with <i>k</i>-Transmitters in the Presence of Obstacles.
Proceedings of the Combinatorial Optimization and Applications, 2010

Common Unfoldings of Polyominoes and Polycubes.
Proceedings of the Computational Geometry, Graphs and Applications, 2010

Oja medians and centers of gravity.
Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 2010

Spanners of Complete k-Partite Geometric Graphs.
SIAM J. Comput., 2009

Algorithms for optimal outlier removal.
J. Discrete Algorithms, 2009

Centerpoint Theorems for Wedges.
Discret. Math. Theor. Comput. Sci., 2009

Connectivity-preserving transformations of binary images.
Comput. Vis. Image Underst., 2009

On the Expected Maximum Degree of Gabriel and Yao Graphs
CoRR, 2009

Rotationally monotone polygons.
Comput. Geom., 2009

Clamshell Casting.
Algorithmica, 2009

Delaunay Triangulation of Imprecise Points Simplified and Extended.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Output-sensitive algorithms for Tukey depth and related problems.
Stat. Comput., 2008

A Characterization of the degree sequences of 2-trees.
J. Graph Theory, 2008

Realizing partitions respecting full and partial order information.
J. Discrete Algorithms, 2008

On the false-positive rate of Bloom filters.
Inf. Process. Lett., 2008

A Polynomial Bound for Untangling Geometric Planar Graphs.
Electron. Notes Discret. Math., 2008

Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles in 2D and 3D.
Discret. Comput. Geom., 2008

An optimal randomized algorithm for d-variate zonoid depth.
Comput. Geom., 2008

Algorithms for bivariate zonoid depth.
Comput. Geom., 2008

Edge-unfolding nested polyhedral bands.
Comput. Geom., 2008

Distinct Distances in Graph Drawings.
Electron. J. Comb., 2008

Distribution-sensitive point location in convex subdivisions.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Randomized Rendez-Vous with Limited Memory.
Proceedings of the LATIN 2008: Theoretical Informatics, 2008

Simultaneous diagonal flips in plane triangulations.
J. Graph Theory, 2007

Geodesic Ham-Sandwich Cuts.
Discret. Comput. Geom., 2007

Space-efficient geometric divide-and-conquer algorithms.
Comput. Geom., 2007

Reconfiguring Triangulations with Edge Flips and Point Moves.
Algorithmica, 2007

Removing Outliers to Minimize Area and Perimeter.
Proceedings of the 18th Annual Canadian Conference on Computational Geometry, 2006

Layout of Graphs with Bounded Tree-Width.
SIAM J. Comput., 2005

Range Mode and Range Median Queries on Lists and Trees.
Nord. J. Comput., 2005

Covering Things with Things.
Discret. Comput. Geom., 2005

Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries.
Discret. Comput. Geom., 2005

Guest Editors' Foreword.
Algorithmica, 2005

Approximate Range Mode and Range Median Queries.
Proceedings of the STACS 2005, 2005

Hash Tables.
Proceedings of the Handbook of Data Structures and Applications., 2004

Space-efficient planar convex hull algorithms.
Theor. Comput. Sci., 2004

Competitive online routing in geometric graphs.
Theor. Comput. Sci., 2004

On Worst-Case Robin Hood Hashing.
SIAM J. Comput., 2004

Online Routing in Triangulations.
SIAM J. Comput., 2004

Three-Dimensional 1-Bend Graph Drawings.
J. Graph Algorithms Appl., 2004

The Maximum Number of Edges in a Three-Dimensional Grid-Drawing.
J. Graph Algorithms Appl., 2004

Packing two disks into a polygonal environment.
J. Discrete Algorithms, 2004

The geometry of carpentry and joinery.
Discret. Appl. Math., 2004

Ordered theta graphs.
Comput. Geom., 2004

On simplifying dot maps.
Comput. Geom., 2004

Testing the Quality of Manufactured Disks and Balls.
Algorithmica, 2004

Unfolding polyhedral bands.
Proceedings of the 16th Canadian Conference on Computational Geometry, 2004

Improving Distance Based Geographic Location Techniques in Sensor Networks.
Proceedings of the Ad-Hoc, Mobile, and Wireless Networks: Third International Conference, 2004

Asymmetric Communication Protocols via Hotlink Assignments.
Theory Comput. Syst., 2003

Cuckoo hashing: Further analysis.
Inf. Process. Lett., 2003

Computing the Center of Area of a Convex Polygon.
Int. J. Comput. Geom. Appl., 2003

Fast approximations for sums of distances, clustering and the Fermat-Weber problem.
Comput. Geom., 2003

Translating a regular grid over a point set.
Comput. Geom., 2003

Bounds for Frequency Estimation of Packet Streams.
Proceedings of the SIROCCO 10: Proceedings of the 10th Internaltional Colloquium on Structural Information Complexity, 2003

An Improved Algorithm for Subdivision Traversal without Extra Storage.
Int. J. Comput. Geom. Appl., 2002

Online Routing in Convex Subdivisions.
Int. J. Comput. Geom. Appl., 2002

Computing the Maximum Detour and Spanning Ratio of Planar Paths, Trees, and Cycles.
Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

In-Place Planar Convex Hull Algorithms.
Proceedings of the LATIN 2002: Theoretical Informatics, 2002

Succinct Data Structures for Approximating Convex Functions with Applications.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2002

Path-Width and Three-Dimensional Straight-Line Grid Drawings of Graphs.
Proceedings of the Graph Drawing, 10th International Symposium, 2002

Routing with Guaranteed Delivery in Ad Hoc Wireless Networks.
Wirel. Networks, 2001

Convexifying polygons with simple projections.
Inf. Process. Lett., 2001

The Grid Placement Problem.
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

Flipping your Lid.
Proceedings of the 12th Canadian Conference on Computational Geometry, 2000

Testing the Quality of Manufactured Balls.
Proceedings of the Algorithms and Data Structures, 6th International Workshop, 1999

Coarse grained parallel computing on heterogeneous systems.
Proceedings of the 1998 ACM symposium on Applied Computing, 1998

Testing the Quality of Manufactured Disks and Cylinders.
Proceedings of the Algorithms and Computation, 9th International Symposium, 1998

Progressive TINs: Algorithms and Applications.
Proceedings of the GIS '97. Proceedings of the 5th International Workshop on Advances in Geographic Information Systems, 1997