1 Search Results for "Odak, Saeed"

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-dev.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}
}
  • Refine by Author
  • 1 Bose, Prosenjit
  • 1 Morin, Pat
  • 1 Odak, Saeed

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph theory

  • Refine by Keyword
  • 1 Planar graphs
  • 1 product structure

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

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 Imprint Privacy Contact