Search Results

Documents authored by Odak, Saeed

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.GD.2024.36
Noncrossing Longest Paths and Cycles

Authors: Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Saeed Odak, Michiel Smid, Csaba D. Tóth, and Pavel Valtr

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

Abstract
Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short geometric structures such as shortest perfect matchings, shortest spanning trees, shortest spanning paths, and shortest spanning cycles on a given point set are inherently noncrossing. However, the longest such structures need not be noncrossing. In fact, it is intuitive to expect many edge crossings in various geometric graphs that are longest. Recently, Álvarez-Rebollar, Cravioto-Lagos, Marín, Solé-Pi, and Urrutia (Graphs and Combinatorics, 2024) constructed a set of points for which the longest perfect matching is noncrossing. They raised several challenging questions in this direction. In particular, they asked whether the longest spanning path, on any finite set of points in the plane, must have a pair of crossing edges. They also conjectured that the longest spanning cycle must have a pair of crossing edges. In this paper, we give a negative answer to the question and also refute the conjecture. We present a framework for constructing arbitrarily large point sets for which the longest perfect matchings, the longest spanning paths, and the longest spanning cycles are noncrossing.
Cite as

Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Saeed Odak, Michiel Smid, Csaba D. Tóth, and Pavel Valtr. Noncrossing Longest Paths and Cycles. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aloupis_et_al:LIPIcs.GD.2024.36,
  author =	{Aloupis, Greg and Biniaz, Ahmad and Bose, Prosenjit and De Carufel, Jean-Lou and Eppstein, David and Maheshwari, Anil and Odak, Saeed and Smid, Michiel and T\'{o}th, Csaba D. and Valtr, Pavel},
  title =	{{Noncrossing Longest Paths and Cycles}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{36:1--36: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.36},
  URN =		{urn:nbn:de:0030-drops-213203},
  doi =		{10.4230/LIPIcs.GD.2024.36},
  annote =	{Keywords: Longest Paths, Longest Cycles, Noncrossing Paths, Noncrossing Cycles}
}
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}
}
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