Pat Morin | DeepAI

DeepAI AI Chat

Featured Co-authors

David Eppstein
67 publications
Giuseppe Liotta
39 publications
Therese Biedl
39 publications
Fabrizio Montecchiani
37 publications
Prosenjit Bose
34 publications
Michael Kaufmann
34 publications
Torsten Ueckerdt
34 publications
Gwenaël Joret
32 publications
David R. Wood
29 publications
Joachim Gudmundsson
28 publications
Birgit Vogtenhuber
28 publications

∙ 08/25/2023

Min-k-planar Drawings of Graphs

The study of nonplanar drawings of graphs with restricted crossing confi...

0 Carla Binucci, et al. ∙

∙ 07/06/2023

The grid-minor theorem revisited

We prove that for every planar graph X of treedepth h, there exists a po...

0 Vida Dujmovic, et al. ∙

∙ 06/09/2023

Proof of the Clustered Hadwiger Conjecture

Hadwiger's Conjecture asserts that every K_h-minor-free graph is properl...

0 Vida Dujmovic, et al. ∙

∙ 03/27/2023

The Excluded Tree Minor Theorem Revisited

We prove that for every tree T of radius h, there is an integer c such t...

0 Vida Dujmovic, et al. ∙

∙ 05/30/2022

Linear versus centred chromatic numbers

We prove that the linear chromatic number of any k× k pseudogrid is Ω(k)...

0 Prosenjit Bose, et al. ∙

∙ 02/17/2022

An Optimal Algorithm for Product Structure in Planar Graphs

The Product Structure Theorem for planar graphs (Dujmović et al.JACM, 67...

0 Prosenjit Bose, et al. ∙

∙ 05/05/2021

2× n Grids have Unbounded Anagram-Free Chromatic Number

We show that anagram-free vertex colouring a 2× n square grid requires a...

0 Saman Bazarghani, et al. ∙

∙ 05/04/2021

Separating layered treewidth and row treewidth

Layered treewidth and row treewidth are recently introduced graph parame...

0 Prosenjit Bose, et al. ∙

∙ 11/09/2020

Stack-number is not bounded by queue-number

We describe a family of graphs with queue-number at most 4 but unbounded...

0 Vida Dujmovic, et al. ∙

∙ 10/12/2020

Sparse universal graphs for planarity

We show that for every integer n≥ 1 there exists a graph G_n with (1+o(1...

0 Louis Esperet, et al. ∙

∙ 07/13/2020

Asymptotically Optimal Vertex Ranking of Planar Graphs

A (vertex) ℓ-ranking is a labelling φ:V(G)→ℕ of the vertices of a graph ...

0 Prosenjit Bose, et al. ∙

∙ 04/07/2020

Two Results on Layered Pathwidth and Linear Layouts

Layered pathwidth is a new graph parameter studied by Bannister et al (2...

0 Vida Dujmovic, et al. ∙

∙ 04/06/2020

A Fast Algorithm for the Product Structure of Planar Graphs

Dujmović et al (FOCS2019) recently proved that every planar graph G is a...

0 Pat Morin, et al. ∙

∙ 03/09/2020

Adjacency Labelling for Planar Graphs (and Beyond)

We show that there exists an adjacency labelling scheme for planar graph...

0 Vida Dujmovic, et al. ∙

∙ 02/13/2020

Drawing Graphs as Spanners

We study the problem of embedding graphs in the plane as good geometric ...

0 Oswin Aichholzer, et al. ∙

∙ 07/11/2019

The structure of k-planar graphs

Dujmović et al. (FOCS 2019) recently proved that every planar graph is a...

0 Vida Dujmovic, et al. ∙

∙ 04/09/2019

Planar Graphs have Bounded Queue-Number

We show that planar graphs have bounded queue-number, thus proving a con...

0 Vida Dujmovic, et al. ∙

∙ 03/06/2019

Encoding 3SUM

We consider the following problem: given three sets of real numbers, out...

0 Sergio Cabello, et al. ∙

∙ 01/17/2019

Queue Layouts of Graphs with Bounded Degree and Bounded Genus

We prove that graphs with bounded degree and bounded Euler genus have bo...

0 Vida Dujmovic, et al. ∙

∙ 12/24/2018

Near-Optimal O(k)-Robust Geometric Spanners

For any constants d> 1, ϵ >0, t>1, and any n-point set P⊂R^d, we show th...

0 Prosenjit Bose, et al. ∙

∙ 12/17/2018

Stabbing Pairwise Intersecting Disks by Four Points

Following the seminal works of Danzer (1956, 1986) and Stachó (1965,1981...

0 Ahmad Biniaz, et al. ∙

∙ 10/19/2018

Minor-closed graph classes with bounded layered pathwidth

We prove that a minor-closed class of graphs has bounded layered pathwid...

0 Vida Dujmovic, et al. ∙

∙ 03/09/2018

Geodesic Obstacle Representation of Graphs

An obstacle representation of a graph is a mapping of the vertices onto ...

0 Prosenjit Bose, et al. ∙

∙ 08/31/2017

EPG-representations with small grid-size

In an EPG-representation of a graph G each vertex is represented by a pa...

0 Therese Biedl, et al. ∙

∙ 06/30/2017

More Turán-Type Theorems for Triangles in Convex Point Sets

We study the following family of problems: Given a set of n points in co...

0 Boris Aronov, et al. ∙

∙ 01/15/2010

Planar Visibility: Testing and Counting

In this paper we consider query versions of visibility testing and visib...

0 Joachim Gudmundsson, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world