Výsledky vyhledávání

Akademický článek

Graphs Drawn With Some Vertices per Face: Density and Relationships

Autor: Carla Binucci, Giuseppe Di Battista, Walter Didimo, Vida Dujmovic, Seok-Hee Hong, Michael Kaufmann, Giuseppe Liotta, Pat Morin, Alessandra Tappini

Publikováno v: IEEE Access, Vol 12, Pp 68828-68846 (2024)

Graph drawing beyond planarity is a research area that has received an increasing attention in the last twenty years, driven by the necessity to mitigate the visual complexity inherent in geometric representations of non-planar graphs. This research

Externí odkaz: https://doaj.org/article/678bca8bfdb449b7bf54ecc84a394fb6

Zobrazit plný text záznamu

Akademický článek

Separating layered treewidth and row treewidth

Autor: Prosenjit Bose, Vida Dujmović, Mehrnoosh Javarsineh, Pat Morin, David R. Wood

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol vol. 24, no. 1, Iss Graph Theory (2022)

Layered treewidth and row treewidth are recently introduced graph parameters that have been key ingredients in the solution of several well-known open problems. It follows from the definitions that the layered treewidth of a graph is at most its row

Externí odkaz: https://doaj.org/article/d23df7fef3614138ab44ebc16c748c5b

Zobrazit plný text záznamu

Akademický článek

Centerpoint theorems for wedges

Autor: Jeff Erickson, Ferran Hurtado, Pat Morin

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol Vol. 11 no. 1 (2009)

General

Externí odkaz: https://doaj.org/article/feae77522f6e41e6a55ad929861baa64

Zobrazit plný text záznamu

Elektronická kniha

Open Data Structures : An Introduction

Autor: Pat Morin

Offered as an introduction to the field of data structures and algorithms, Open Data Structures covers the implementation and analysis of data structures for sequences (lists), queues, priority queues, unordered dictionaries, ordered dictionaries, an

Zobrazit plný text záznamu

Minor-Closed Graph Classes with Bounded Layered Pathwidth

Autor: David R. Wood, Pat Morin, Gwenaël Joret, Vida Dujmović, David Eppstein

Publikováno v: SIAM journal on discrete mathematics, 34 (3

We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if some apex-forest is not in the class. This generalises a theorem of Robertson and Seymour, which says that a minor-closed class of graphs has bounded pathwidth

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5597d995adec1e8371ef6613f9b015a3
https://doi.org/10.1137/18m122162x

Zobrazit plný text záznamu

Notes on growing a tree in a graph

Autor: Vida Dujmović, Bruce Reed, Alan Frieze, Pat Morin, Abbas Mehrabian, Luc Devroye

Publikováno v: Random Structures & Algorithms. 55:290-312

We study the height of a spanning tree $T$ of a graph $G$ obtained by starting with a single vertex of $G$ and repeatedly selecting, uniformly at random, an edge of $G$ with exactly one endpoint in $T$ and adding this edge to $T$.

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::749745b02f3cbc8e384aeda3796f0412
https://doi.org/10.1002/rsa.20828

Zobrazit plný text záznamu

$2\times n$ Grids have Unbounded Anagram-Free Chromatic Number

Autor: Saman Bazarghani, Paz Carmi, Vida Dujmović, Pat Morin

We show that anagram-free vertex colouring a $2\times n$ square grid requires a number of colours that increases with $n$. This answers an open question in Wilson's thesis and shows that even graphs of pathwidth $2$ do not have anagram-free colouring

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b9148a49356d82e3521270114032a173
http://arxiv.org/abs/2105.01916

Zobrazit plný text záznamu

Elektronická kniha

Algorithms and Data Structures : 18th International Symposium, WADS 2023, Montreal, QC, Canada, July 31 – August 2, 2023, Proceedings

Autor: Pat Morin, Subhash Suri

This book constitutes the refereed proceedings of the 18th International Symposium on Algorithms and Data Structures, WADS 2023, held during July 31-August 2, 2023. The 47 regular papers, presented in this book, were carefully reviewed and selected f

Zobrazit plný text záznamu

Clustered 3-Colouring Graphs of Bounded Degree

Autor: Louis Esperet, David R. Wood, Bartosz Walczak, Vida Dujmović, Pat Morin

Publikováno v: Combinatorics, Probability and Computing
Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2022, 31 (1), pp.123-135. ⟨10.1017/S0963548321000213⟩

A (not necessarily proper) vertex colouring of a graph has "clustering" $c$ if every monochromatic component has at most $c$ vertices. We prove that planar graphs with maximum degree $\Delta$ are 3-colourable with clustering $O(\Delta^2)$. The previo

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3afa0ab49f9e645afb0338961830dbff
http://arxiv.org/abs/2002.11721

Zobrazit plný text záznamu

Drawing Graphs as Spanners

Autor: Manuel Borrazzo, Prosenjit Bose, Oswin Aichholzer, Fabrizio Frati, Pat Morin, Jean Cardinal, Birgit Vogtenhuber

Publikováno v: 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020)
Graph-Theoretic Concepts in Computer Science ISBN: 9783030604394
WG
Discrete & Computational Geometry
Lecture Notes in Computer Science
Lecture Notes in Computer Science-Graph-Theoretic Concepts in Computer Science

We study the problem of embedding graphs in the plane as good geometric spanners. That is, for a graph $G$, the goal is to construct a straight-line drawing $\Gamma$ of $G$ in the plane such that, for any two vertices $u$ and $v$ of $G$, the ratio be

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7b1e302c67c88f8d2bdd82d685003e8c

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání