Publications

• Erdős-Pósa property of cycles that are far apart Vida Dujmovic, Gwenaël Joret, Piotr Micek, and Pat Morin CoRR, vol. abs/2412.13893, 2024
  DOI
• Tight Bounds on the Number of Closest Pairs in Vertical Slabs Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung, Jean-Lou De Carufel, John Iacono, Anil Maheshwari, Saeed Odak, Michiel Smid, and Csaba D. Tóth CoRR, vol. abs/2502.17600, 2025
  DOI
• Quasi-isometries between graphs with variable edge lengths James Davies, Meike Hatzel, and Robert Hickingbotham CoRR, vol. abs/2503.07448, 2025
  DOI
• Planar Graphs in Blowups of Fans Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, and David R. Wood Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), pp. 3382–3391, 2025
  DOI
• Minimum Plane Bichromatic Spanning Trees Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine, Linda Kleist, Frederick Stock, and Csaba D. Tóth 35th International Symposium on Algorithms and Computation (ISAAC 2024), LIPIcs vol. 322, pp. 4:1–4:14, 2024
  DOI
• Noncrossing Longest Paths and Cycles Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Saeed Odak, Michiel Smid, Csaba D. Tóth, and Pavel Valtr 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024), LIPIcs vol. 320, pp. 36:1–36:17, 2024
  DOI
• On the Spanning and Routing Ratio of the Directed Theta-Four Graph Prosenjit Bose, Jean-Lou De Carufel, Darryl Hill, and Michiel Smid Discrete & Computational Geometry, vol. 71, no. 3, pp. 872–892, 2024
  DOI
• Fat minors cannot be thinned James Davies and Yelena Yuditsky CoRR, vol. abs/2407.16882, 2024
  DOI
• Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity James Davies and Yelena Yuditsky CoRR, vol. abs/2407.16882, 2024
  DOI
• Product Structure Extension of the Alon-Seymour-Thomas Theorem Marc Distel, Vida Dujmovic, David Eppstein, Robert Hickingbotham, Gwenaël Joret, Piotr Micek, Pat Morin, Michal T. Seweryn, and David R. Wood SIAM Journal on Discrete Mathematics, vol. 38, no. 3, pp. 2095–2107, 2024
  DOI
• The Excluded Tree Minor Theorem Revisited Vida Dujmović, Robert Hickingbotham, Gwenaël Joret, Piotr Micek, Pat Morin, and David R. Wood Combinatorics, Probability and Computing, vol. 33, no. 1, pp. 85–90, 2024
  DOI
• Vertex ranking of degenerate graphs John Iacono, Piotr Micek, Pat Morin, and Bruce Reed CoRR, vol. abs/2404.16340, 2024
  DOI
• The Minimum Moving Spanning Tree Problem Hugo A. Akitaya, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari, Luís Fernando Schultz Xavier da Silveira, and Michiel Smid Journal of Graph Algorithms and Applications, vol. 27, no. 1, pp. 1–18, 2023
  DOI
• Piercing Unit Geodesic Disks Ahmad Biniaz, Prosenjit Bose, and Thomas C. Shermer Proceedings of the 35th Canadian Conference on Computational Geometry (CCCG 2023), pp. 43–49, 2023
• Improved Routing on the Delaunay Triangulation Nicolas Bonichon, Prosenjit Bose, Jean-Lou De Carufel, Vincent Despré, Darryl Hill, and Michiel Smid Discrete & Computational Geometry, vol. 70, no. 3, pp. 495–549, 2023
• Subtrajectory Clustering: Finding Set Covers for Set Systems of Subcurves F. Brüning, H. Akitaya, E. Chambers, and A. Driemel Computing in Geometry and Topology, vol. 2, no. 1, pp. 1:1–1:48, 2023
• Finding Complex Patterns in Trajectory Data via Geometric Set Cover Jacobus Conradi and Anne Driemel CoRR, vol. abs/2308.14865, 2023
  DOI
• Proof of the Clustered Hadwiger Conjecture Vida Dujmović, Louis Esperet, Pat Morin, and David R. Wood 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2023), pp. 1921–1930, 2023
  DOI
• Geometric Graphs with Unbounded Flip-Width David Eppstein and Rose McCarty CoRR, vol. abs/2306.12611, 2023
  DOI
• Universal geometric graphs Fabrizio Frati, Michael Hoffmann, and Csaba D. Tóth Combinatorics, Probability and Computing, vol. 32, no. 5, pp. 742–761, 2023
  DOI
• Cop-width, flip-width and strong colouring numbers Robert Hickingbotham CoRR, vol. abs/2309.05874, 2023
  DOI
• On RAC Drawings of Graphs with Two Bends per Edge Csaba D. Tóth Graph Drawing and Network Visualization (GD 2023), LNCS vol. 14465, pp. 69–77, 2023
  DOI
• On the spanning and routing ratios of the directed Θ₆-graph Hugo A. Akitaya, Ahmad Biniaz, and Prosenjit Bose Computational Geometry, vol. 105-106, pp. 101881, 2022
  DOI
• Bounded-Angle Minimum Spanning Trees Ahmad Biniaz, Prosenjit Bose, Anna Lubiw, and Anil Maheshwari Algorithmica, vol. 84, no. 1, pp. 150–175, 2022
  DOI
• Shorter Labeling Schemes for Planar Graphs Marthe Bonamy, Cyril Gavoille, and Michal Pilipczuk SIAM Journal on Discrete Mathematics, vol. 36, no. 3, pp. 2082–2099, 2022
  DOI
• Linear versus centred chromatic numbers Prosenjit Bose, Vida Dujmović, Hussein Houdrouge, Mehrnoosh Javarsineh, and Pat Morin CoRR, vol. abs/2205.15096, 2022
  DOI
• Faster Approximate Covering of Subcurves Under the Fréchet Distance Frederik Brüning, Jacobus Conradi, and Anne Driemel 30th Annual European Symposium on Algorithms (ESA 2022), LIPIcs vol. 244, pp. 28:1–28:16, 2022
  DOI
• Adjacency Labelling for Planar Graphs (and Beyond) Vida Dujmovic, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, and Pat Morin Journal of the ACM, vol. 68, no. 6, pp. 42:1–42:33, 2021
  DOI
• Upward Point Set Embeddings of Paths and Trees Elena Arseneva, Pilar Cano, Linda Kleist, Tamara Mchedlidze, Saeed Mehrabi, Irene Parada, and Pavel Valtr WALCOM: Algorithms and Computation 2021, LNCS vol. 12635, pp. 234–246, 2021
  DOI
• On the Minimum Consistent Subset Problem Ahmad Biniaz, Sergio Cabello, Paz Carmi, Jean-Lou De Carufel, Anil Maheshwari, Saeed Mehrabi, and Michiel Smid Algorithmica, vol. 83, no. 7, pp. 2273–2302, 2021
  DOI
• Adjacency Labelling for Planar Graphs (and Beyond) Vida Dujmović, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, and Pat Morin Journal of the ACM, vol. 68, no. 6, pp. 42:1–42:33, 2021
  DOI
• Tight Bounds on the Clique Chromatic Number Gwenaël Joret, Piotr Micek, Bruce A. Reed, and Michiel Smid Electronic Journal of Combinatorics, vol. 28, no. 3, 2021
  DOI
• A Fast Algorithm for the Product Structure of Planar Graphs Pat Morin Algorithmica, vol. 83, no. 5, pp. 1544–1558, 2021
  DOI
• Simple k-planar graphs are simple k+1-quasiplanar Patrizio Angelini, Michael A. Bekos, Franz J. Brandenburg, Giordano Da Lozzo, Giuseppe Di Battista, Walter Didimo, Michael Hoffmann, Giuseppe Liotta, Fabrizio Montecchiani, Ignaz Rutter, and Csaba D. Tóth Journal of Combinatorial Theory, Series B, vol. 142, pp. 1–35, 2020
  DOI
• Planar Graphs Have Bounded Queue-Number Vida Dujmovic, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood Journal of the ACM, vol. 67, no. 4, pp. 22:1–22:38, 2020
  DOI
• Resolving SINR Queries in a Dynamic Setting Boris Aronov, Gali Bar-On, and Matthew J. Katz SIAM Journal on Computing, vol. 49, no. 6, pp. 1271–1290, 2020
  DOI
• Shorter Labeling Schemes for Planar Graphs Marthe Bonamy, Cyril Gavoille, and Michal Pilipczuk Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pp. 446–462, 2020
  DOI
• Spanning Properties of Theta-Theta-6 Mirela Damian, John Iacono, and Andrew Winslow Graphs and Combinatorics, vol. 36, no. 3, pp. 525–538, 2020
  DOI
• Adjacency Labelling for Planar Graphs (and Beyond) Vida Dujmović, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, and Pat Morin 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2020), pp. 577–588, 2020
  DOI
• Planar Graphs Have Bounded Queue-Number Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood Journal of the ACM, vol. 67, no. 4, pp. 22:1–22:38, 2020
  DOI
• Long Alternating Paths Exist Wolfgang Mulzer and Pavel Valtr 36th International Symposium on Computational Geometry (SoCG 2020), LIPIcs vol. 164, pp. 57:1–57:16, 2020
  DOI
• A simple randomized O(n log n)-time closest-pair algorithm in doubling metrics Michiel Smid, Anil Maheshwari, and Wolfgang Mulzer Journal of Computational Geometry, vol. 11, no. 1, pp. 507–524, 2020
  DOI
• More Turán-Type Theorems for Triangles in Convex Point Sets Boris Aronov, Vida Dujmović, Pat Morin, Aurélien Ooms, and Luís Fernando Schultz Xavier da Silveira Electronic Journal of Combinatorics, vol. 26, no. 1, pp. 1, 2019
  DOI
• Asymmetric Convex Intersection Testing Luis Barba and Wolfgang Mulzer 2nd Symposium on Simplicity in Algorithms (SOSA 2019), OASIcs vol. 69, pp. 9:1–9:14, 2019
  DOI
• Covering many points with a small-area box Mark de Berg, Sergio Cabello, Otfried Cheong, David Eppstein, and Christian Knauer Journal of Computational Geometry, vol. 10, no. 1, pp. 207–222, 2019
  DOI
• Three-Coloring Three-Dimensional Uniform Hypergraphs Ahmad Biniaz, Prosenjit Bose, Jean Cardinal, and Michael S. Payne Proceedings of the 31st Canadian Conference on Computational Geometry (CCCG 2019), pp. 23–28, 2019
• On the Minimum Consistent Subset Problem Ahmad Biniaz, Sergio Cabello, Paz Carmi, Jean-Lou De Carufel, Anil Maheshwari, Saeed Mehrabi, and Michiel Smid H. M. Algorithms and Data Structures (WADS 2019), LNCS vol. 11646, pp. 155–167, 2019
  DOI
• Every Collinear Set in a Planar Graph Is Free Vida Dujmović, Fabrizio Frati, Daniel Gonçalves, Pat Morin, and Günter Rote Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pp. 1521–1538, 2019
  DOI
• Planar Graphs have Bounded Queue-Number Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2019), pp. 862–875, 2019
  DOI
• Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time David Eppstein and Bruce A. Reed Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pp. 589–605, 2019
  DOI
• Simultaneous Embeddings with Few Bends and Crossings Fabrizio Frati, Michael Hoffmann, and Vincent Kusters Journal of Graph Algorithms and Applications, vol. 23, no. 4, pp. 683–713, 2019
  DOI
• A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations Anna Lubiw, Zuzana Masárová, and Uli Wagner Discrete & Computational Geometry, vol. 61, no. 4, pp. 880–898, 2019
  DOI
• A Logarithmic bound for the chromatic number of the associahedron Louigi Addario-Berry, Bruce Reed, Alex Scott, and David R. Wood CoRR, vol. abs/1811.08972v2, 2018
  DOI
• Continuous Yao graphs Davood Bakhshesh, Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, Mirela Damian, Rolf Fagerberg, Mohammad Farshi, André van Renssen, Perouz Taslakian, and Sander Verdonschot Computational Geometry, vol. 67, pp. 42–52, 2018
  DOI
• EPG-representations with Small Grid-Size Therese Biedl, Martin Derka, Vida Dujmović, and Pat Morin Graph Drawing and Network Visualization (GD 2017), LNCS vol. 10692, pp. 184–196, 2017
  DOI
• Towards plane spanners of degree 3 Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, Anil Maheshwari, and Michiel Smid H. M. Journal of Computational Geometry, vol. 8, no. 1, pp. 11–31, 2017
  DOI
• New Bounds for Facial Nonrepetitive Colouring Prosenjit Bose, Vida Dujmović, Pat Morin, and Lucas Rioux-Maldague Graphs and Combinatorics, vol. 33, no. 4, pp. 817–832, 2017
  DOI
• Structure of Graphs with Locally Restricted Crossings Vida Dujmović, David Eppstein, and David R. Wood SIAM Journal on Discrete Mathematics, vol. 31, no. 2, pp. 805–824, 2017
  DOI
• Two-Planar Graphs Are Quasiplanar Michael Hoffmann and Csaba D. Tóth 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), LIPIcs vol. 83, pp. 47:1–47:14, 2017
  DOI
• A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations Anna Lubiw, Zuzana Masárová, and Uli Wagner 33rd International Symposium on Computational Geometry (SoCG 2017), LIPIcs vol. 77, pp. 49:1–49:15, 2017
  DOI
• Towards Plane Spanners of Degree 3 Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, Anil Maheshwari, and Michiel Smid H. M. 27th International Symposium on Algorithms and Computation (ISAAC 2016), LIPIcs vol. 64, pp. 19:1–19:14, 2016
  DOI
• Layouts of graph expanders Vida Dujmović, Anastasios Sidiropoulos, and David R. Wood Chicago Journal of Theoretical Computer Science, vol. 16, no. 1, 2016
• Analysis of farthest point sampling for approximating geodesics in a graph Pegah Kamousi, Sylvain Lazard, Anil Maheshwari, and Stefanie Wuhrer Computational Geometry, vol. 57, pp. 1–7, 2016
  DOI
• Compatible Connectivity Augmentation of Planar Disconnected Graphs Greg Aloupis, Luis Barba, Paz Carmi, Vida Dujmović, Fabrizio Frati, and Pat Morin Discrete & Computational Geometry, vol. 54, no. 2, pp. 459–480, 2015
  DOI
• Compatible Connectivity-Augmentation of Planar Disconnected Graphs Greg Aloupis, Luis Barba, Paz Carmi, Vida Dujmović, Fabrizio Frati, and Pat Morin Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pp. 1602–1615, 2015
  DOI
• New and improved spanning ratios for Yao graphs Luis Barba, Prosenjit Bose, Mirela Damian, Rolf Fagerberg, Wah Loon Keng, Joseph O'Rourke, André van Renssen, Perouz Taslakian, Sander Verdonschot, and Ge Xia Journal of Computational Geometry, vol. 6, no. 2, pp. 19–53, 2015
  DOI
• Genus, Treewidth, and Local Crossing Number Vida Dujmović, David Eppstein, and David R. Wood Graph Drawing and Network Visualization (GD 2015), LNCS vol. 9411, pp. 87–98, 2015
  DOI
• On Obstacle Numbers Vida Dujmović and Pat Morin Electronic Journal of Combinatorics, vol. 22, no. 3, pp. 3, 2015
  DOI
• Simultaneous Embeddings with Few Bends and Crossings Fabrizio Frati, Michael Hoffmann, and Vincent Kusters Graph Drawing and Network Visualization (GD 2015), LNCS vol. 9411, pp. 166–179, 2015
  DOI
• On k-Enclosing Objects in a Coloured Point Set Luis Barba, Stephane Durocher, Robert Fraser, Ferran Hurtado, Saeed Mehrabi, Debajyoti Mondal, Jason Morrison, Matthew Skala, and Mohammad Abdul Wahid Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), 2013
  PDF