Search Results

Documents authored by Morin, Pat

Document
DOI: 10.4230/LIPIcs.GD.2024.27
On k-Planar Graphs Without Short Cycles

Authors: Michael A. Bekos, Prosenjit Bose, Aaron Büngener, Vida Dujmović, Michael Hoffmann, Michael Kaufmann, Pat Morin, Saeed Odak, and Alexandra Weinberger

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
We study the impact of forbidding short cycles to the edge density of k-planar graphs; a k-planar graph is one that can be drawn in the plane with at most k crossings per edge. Specifically, we consider three settings, according to which the forbidden substructures are 3-cycles, 4-cycles or both of them (i.e., girth ≥ 5). For all three settings and all k ∈ {1,2,3}, we present lower and upper bounds on the maximum number of edges in any k-planar graph on n vertices. Our bounds are of the form c n, for some explicit constant c that depends on k and on the setting. For general k ≥ 4 our bounds are of the form c√kn, for some explicit constant c. These results are obtained by leveraging different techniques, such as the discharging method, the recently introduced density formula for non-planar graphs, and new upper bounds for the crossing number of 2- and 3-planar graphs in combination with corresponding lower bounds based on the Crossing Lemma.
Cite as

Michael A. Bekos, Prosenjit Bose, Aaron Büngener, Vida Dujmović, Michael Hoffmann, Michael Kaufmann, Pat Morin, Saeed Odak, and Alexandra Weinberger. On k-Planar Graphs Without Short Cycles. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.GD.2024.27,
  author =	{Bekos, Michael A. and Bose, Prosenjit and B\"{u}ngener, Aaron and Dujmovi\'{c}, Vida and Hoffmann, Michael and Kaufmann, Michael and Morin, Pat and Odak, Saeed and Weinberger, Alexandra},
  title =	{{On k-Planar Graphs Without Short Cycles}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.27},
  URN =		{urn:nbn:de:0030-drops-213117},
  doi =		{10.4230/LIPIcs.GD.2024.27},
  annote =	{Keywords: Beyond-planar Graphs, k-planar Graphs, Local Crossing Number, Crossing Number, Discharging Method, Crossing Lemma}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.48
Local Certification of Geometric Graph Classes

Authors: Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
The goal of local certification is to locally convince the vertices of a graph G that G satisfies a given property. A prover assigns short certificates to the vertices of the graph, then the vertices are allowed to check their certificates and the certificates of their neighbors, and based only on this local view and their own unique identifier, they must decide whether G satisfies the given property. If the graph indeed satisfies the property, all vertices must accept the instance, and otherwise at least one vertex must reject the instance (for any possible assignment of certificates). The goal is to minimize the size of the certificates. In this paper we study the local certification of geometric and topological graph classes. While it is known that in n-vertex graphs, planarity can be certified locally with certificates of size O(log n), we show that several closely related graph classes require certificates of size Ω(n). This includes penny graphs, unit-distance graphs, (induced) subgraphs of the square grid, 1-planar graphs, and unit-square graphs. These bounds are tight up to a constant factor and give the first known examples of hereditary (and even monotone) graph classes for which the certificates must have linear size. For unit-disk graphs we obtain a lower bound of Ω(n^{1-δ}) for any δ > 0 on the size of the certificates, and an upper bound of O(n log n). The lower bounds are obtained by proving rigidity properties of the considered graphs, which might be of independent interest.
Cite as

Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond. Local Certification of Geometric Graph Classes. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{defrain_et_al:LIPIcs.MFCS.2024.48,
  author =	{Defrain, Oscar and Esperet, Louis and Lagoutte, Aur\'{e}lie and Morin, Pat and Raymond, Jean-Florent},
  title =	{{Local Certification of Geometric Graph Classes}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{48:1--48:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.48},
  URN =		{urn:nbn:de:0030-drops-206042},
  doi =		{10.4230/LIPIcs.MFCS.2024.48},
  annote =	{Keywords: Local certification, proof labeling schemes, geometric intersection graphs}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.25
Patricia’s Bad Distributions

Authors: Louigi Addario-Berry, Pat Morin, and Ralph Neininger

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
The height of a random PATRICIA tree built from independent, identically distributed infinite binary strings with arbitrary diffuse probability distribution μ on {0,1}^ℕ is studied. We show that the expected height grows asymptotically sublinearly in the number of leaves for any such μ, but can be made to exceed any specific sublinear growth rate by choosing μ appropriately.
Cite as

Louigi Addario-Berry, Pat Morin, and Ralph Neininger. Patricia’s Bad Distributions. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 25:1-25:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{addarioberry_et_al:LIPIcs.AofA.2024.25,
  author =	{Addario-Berry, Louigi and Morin, Pat and Neininger, Ralph},
  title =	{{Patricia’s Bad Distributions}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{25:1--25:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.25},
  URN =		{urn:nbn:de:0030-drops-204600},
  doi =		{10.4230/LIPIcs.AofA.2024.25},
  annote =	{Keywords: PATRICIA tree, random tree, height of tree, analysis of algorithms}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.19
An Optimal Algorithm for Product Structure in Planar Graphs

Authors: Prosenjit Bose, Pat Morin, and Saeed Odak

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
The Product Structure Theorem for planar graphs (Dujmović et al. JACM, 67(4):22) states that any planar graph is contained in the strong product of a planar 3-tree, a path, and a 3-cycle. We give a simple linear-time algorithm for finding this decomposition as well as several related decompositions. This improves on the previous O(nlog n) time algorithm (Morin. Algorithmica, 85(5):1544-1558).
Cite as

Prosenjit Bose, Pat Morin, and Saeed Odak. An Optimal Algorithm for Product Structure in Planar Graphs. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.SWAT.2022.19,
  author =	{Bose, Prosenjit and Morin, Pat and Odak, Saeed},
  title =	{{An Optimal Algorithm for Product Structure in Planar Graphs}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.19},
  URN =		{urn:nbn:de:0030-drops-161797},
  doi =		{10.4230/LIPIcs.SWAT.2022.19},
  annote =	{Keywords: Planar graphs, product structure}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.29
Dual Circumference and Collinear Sets

Authors: Vida Dujmović and Pat Morin

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We show that, if an n-vertex triangulation T of maximum degree Delta has a dual that contains a cycle of length l, then T has a non-crossing straight-line drawing in which some set, called a collinear set, of Omega(l/Delta^4) vertices lie on a line. Using the current lower bounds on the length of longest cycles in 3-regular 3-connected graphs, this implies that every n-vertex planar graph of maximum degree Delta has a collinear set of size Omega(n^{0.8}/Delta^4). Very recently, Dujmović et al. (SODA 2019) showed that, if S is a collinear set in a triangulation T then, for any point set X subset R^2 with |X|=|S|, T has a non-crossing straight-line drawing in which the vertices of S are drawn on the points in X. Because of this, collinear sets have numerous applications in graph drawing and related areas.
Cite as

Vida Dujmović and Pat Morin. Dual Circumference and Collinear Sets. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dujmovic_et_al:LIPIcs.SoCG.2019.29,
  author =	{Dujmovi\'{c}, Vida and Morin, Pat},
  title =	{{Dual Circumference and Collinear Sets}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.29},
  URN =		{urn:nbn:de:0030-drops-104338},
  doi =		{10.4230/LIPIcs.SoCG.2019.29},
  annote =	{Keywords: Planar graphs, collinear sets, untangling, column planarity, universal point subsets, partial simultaneous geometric drawings}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.23
Geodesic Obstacle Representation of Graphs

Authors: Prosenjit Bose, Paz Carmi, Vida Dujmovic, Saeed Mehrabi, Fabrizio Montecchiani, Pat Morin, and Luis Fernando Schultz Xavier da Silveira

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
An obstacle representation of a graph is a mapping of the vertices onto points in the plane and a set of connected regions of the plane (called obstacles) such that the straight-line segment connecting the points corresponding to two vertices does not intersect any obstacles if and only if the vertices are adjacent in the graph. The obstacle representation and its plane variant (in which the resulting representation is a plane straight-line embedding of the graph) have been extensively studied with the main objective of minimizing the number of obstacles. Recently, Biedl and Mehrabi [Therese C. Biedl and Saeed Mehrabi, 2017] studied non-blocking grid obstacle representations of graphs in which the vertices of the graph are mapped onto points in the plane while the straight-line segments representing the adjacency between the vertices is replaced by the L_1 (Manhattan) shortest paths in the plane that avoid obstacles. In this paper, we introduce the notion of geodesic obstacle representations of graphs with the main goal of providing a generalized model, which comes naturally when viewing line segments as shortest paths in the Euclidean plane. To this end, we extend the definition of obstacle representation by allowing some obstacles-avoiding shortest path between the corresponding points in the underlying metric space whenever the vertices are adjacent in the graph. We consider both general and plane variants of geodesic obstacle representations (in a similar sense to obstacle representations) under any polyhedral distance function in R^d as well as shortest path distances in graphs. Our results generalize and unify the notions of obstacle representations, plane obstacle representations and grid obstacle representations, leading to a number of questions on such representations.
Cite as

Prosenjit Bose, Paz Carmi, Vida Dujmovic, Saeed Mehrabi, Fabrizio Montecchiani, Pat Morin, and Luis Fernando Schultz Xavier da Silveira. Geodesic Obstacle Representation of Graphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.ICALP.2018.23,
  author =	{Bose, Prosenjit and Carmi, Paz and Dujmovic, Vida and Mehrabi, Saeed and Montecchiani, Fabrizio and Morin, Pat and Silveira, Luis Fernando Schultz Xavier da},
  title =	{{Geodesic Obstacle Representation of Graphs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{23:1--23:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.23},
  URN =		{urn:nbn:de:0030-drops-90274},
  doi =		{10.4230/LIPIcs.ICALP.2018.23},
  annote =	{Keywords: Obstacle representation, Grid obstacle representation, Geodesic obstacle representation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.2
Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs

Authors: A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Pat Morin, Michiel Smid, and Shakhar Smorodinsky

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We consider a well studied generalization of the maximum clique problem which is defined as follows. Given a graph G on n vertices and an integer d >= 1, in the maximum diameter-bounded subgraph problem (MaxDBS for short), the goal is to find a (vertex) maximum subgraph of G of diameter at most d. For d=1, this problem is equivalent to the maximum clique problem and thus it is NP-hard to approximate it within a factor n^{1-epsilon}, for any epsilon > 0. Moreover, it is known that, for any d >= 2, it is NP-hard to approximate MaxDBS within a factor n^{1/2 - epsilon}, for any epsilon > 0. In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomial-time constant-factor approximation algorithm for the problem. The approximation ratio of our algorithm does not depend on the diameter d. Even though the algorithm itself is simple, its analysis is rather involved. We combine tools from the theory of hypergraphs with bounded VC-dimension, k-quasi planar graphs, fractional Helly theorems and several geometric properties of unit disk graphs.
Cite as

A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Pat Morin, Michiel Smid, and Shakhar Smorodinsky. Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abuaffash_et_al:LIPIcs.SoCG.2018.2,
  author =	{Abu-Affash, A. Karim and Carmi, Paz and Maheshwari, Anil and Morin, Pat and Smid, Michiel and Smorodinsky, Shakhar},
  title =	{{Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.2},
  URN =		{urn:nbn:de:0030-drops-87152},
  doi =		{10.4230/LIPIcs.SoCG.2018.2},
  annote =	{Keywords: Approximation algorithms, maximum diameter-bounded subgraph, unit disk graphs, fractional Helly theorem, VC-dimension}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact