Search Results

Documents authored by Morin, Pat

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}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact