Search Results

Documents authored by Gutowski, Grzegorz

Document
DOI: 10.4230/LIPIcs.GD.2024.14
Bounding the Treewidth of Outer k-Planar Graphs via Triangulations

Authors: Oksana Firman, Grzegorz Gutowski, Myroslav Kryven, Yuto Okada, and Alexander Wolff

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

Abstract
The treewidth is a structural parameter that measures the tree-likeness of a graph. Many algorithmic and combinatorial results are expressed in terms of the treewidth. In this paper, we study the treewidth of outer k-planar graphs, that is, graphs that admit a straight-line drawing where all the vertices lie on a circle, and every edge is crossed by at most k other edges. Wood and Telle [New York J. Math., 2007] showed that every outer k-planar graph has treewidth at most 3k + 11 using so-called planar decompositions, and later, Auer et al. [Algorithmica, 2016] proved that the treewidth of outer 1-planar graphs is at most 3, which is tight. In this paper, we improve the general upper bound to 1.5k + 2 and give a tight bound of 4 for k = 2. We also establish a lower bound: we show that, for every even k, there is an outer k-planar graph with treewidth k+2. Our new bound immediately implies a better bound on the cop number, which answers an open question of Durocher et al. [GD 2023] in the affirmative. Our treewidth bound relies on a new and simple triangulation method for outer k-planar graphs that yields few crossings with graph edges per edge of the triangulation. Our method also enables us to obtain a tight upper bound of k + 2 for the separation number of outer k-planar graphs, improving an upper bound of 2k + 3 by Chaplick et al. [GD 2017]. We also consider outer min-k-planar graphs, a generalization of outer k-planar graphs, where we achieve smaller improvements.
Cite as

Oksana Firman, Grzegorz Gutowski, Myroslav Kryven, Yuto Okada, and Alexander Wolff. Bounding the Treewidth of Outer k-Planar Graphs via Triangulations. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{firman_et_al:LIPIcs.GD.2024.14,
  author =	{Firman, Oksana and Gutowski, Grzegorz and Kryven, Myroslav and Okada, Yuto and Wolff, Alexander},
  title =	{{Bounding the Treewidth of Outer k-Planar Graphs via Triangulations}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{14:1--14: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.14},
  URN =		{urn:nbn:de:0030-drops-212988},
  doi =		{10.4230/LIPIcs.GD.2024.14},
  annote =	{Keywords: treewidth, outerplanar graphs, outer k-planar graphs, outer min-k-planar graphs, cop number, separation number}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.33
First-Fit Coloring of Forests in Random Arrival Model

Authors: Bartłomiej Bosek, Grzegorz Gutowski, Michał Lasoń, and Jakub Przybyło

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

Abstract
We consider a graph coloring algorithm that processes vertices in order taken uniformly at random and assigns colors to them using First-Fit strategy. We show that this algorithm uses, in expectation, at most (1+o(1))⋅ln n / ln ln n different colors to color any forest with n vertices. We also construct a family of forests that shows that this bound is best possible.
Cite as

Bartłomiej Bosek, Grzegorz Gutowski, Michał Lasoń, and Jakub Przybyło. First-Fit Coloring of Forests in Random Arrival Model. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 33:1-33:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bosek_et_al:LIPIcs.MFCS.2024.33,
  author =	{Bosek, Bart{\l}omiej and Gutowski, Grzegorz and Laso\'{n}, Micha{\l} and Przyby{\l}o, Jakub},
  title =	{{First-Fit Coloring of Forests in Random Arrival Model}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{33:1--33:10},
  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.33},
  URN =		{urn:nbn:de:0030-drops-205892},
  doi =		{10.4230/LIPIcs.MFCS.2024.33},
  annote =	{Keywords: First-Fit, Online Algorithms, Graph Coloring, Random Arrival Model}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.36
Coloring and Recognizing Mixed Interval Graphs

Authors: Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen, Paweł Rzążewski, Alexander Wolff, and Johannes Zink

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
A mixed interval graph is an interval graph that has, for every pair of intersecting intervals, either an arc (directed arbitrarily) or an (undirected) edge. We are particularly interested in scenarios where edges and arcs are defined by the geometry of intervals. In a proper coloring of a mixed interval graph G, an interval u receives a lower (different) color than an interval v if G contains arc (u,v) (edge {u,v}). Coloring of mixed graphs has applications, for example, in scheduling with precedence constraints; see a survey by Sotskov [Mathematics, 2020]. For coloring general mixed interval graphs, we present a min {ω(G), λ(G)+1}-approximation algorithm, where ω(G) is the size of a largest clique and λ(G) is the length of a longest directed path in G. For the subclass of bidirectional interval graphs (introduced recently for an application in graph drawing), we show that optimal coloring is NP-hard. This was known for general mixed interval graphs. We introduce a new natural class of mixed interval graphs, which we call containment interval graphs. In such a graph, there is an arc (u,v) if interval u contains interval v, and there is an edge {u,v} if u and v overlap. We show that these graphs can be recognized in polynomial time, that coloring them with the minimum number of colors is NP-hard, and that there is a 2-approximation algorithm for coloring.
Cite as

Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen, Paweł Rzążewski, Alexander Wolff, and Johannes Zink. Coloring and Recognizing Mixed Interval Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gutowski_et_al:LIPIcs.ISAAC.2023.36,
  author =	{Gutowski, Grzegorz and Junosza-Szaniawski, Konstanty and Klesen, Felix and Rz\k{a}\.{z}ewski, Pawe{\l} and Wolff, Alexander and Zink, Johannes},
  title =	{{Coloring and Recognizing Mixed Interval Graphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{36:1--36:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.36},
  URN =		{urn:nbn:de:0030-drops-193388},
  doi =		{10.4230/LIPIcs.ISAAC.2023.36},
  annote =	{Keywords: Interval Graphs, Mixed Graphs, Graph Coloring}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.52
Online Coloring of Short Intervals

Authors: Joanna Chybowska-Sokół, Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Patryk Mikos, and Adam Polak

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
We study the online graph coloring problem restricted to the intersection graphs of intervals with lengths in [1,σ]. For σ = 1 it is the class of unit interval graphs, and for σ = ∞ the class of all interval graphs. Our focus is on intermediary classes. We present a (1+σ)-competitive algorithm, which beats the state of the art for 1 < σ < 2, and proves that the problem we study can be strictly easier than online coloring of general interval graphs. On the lower bound side, we prove that no algorithm is better than 5/3-competitive for any σ > 1, nor better than 7/4-competitive for any σ > 2, and that no algorithm beats the 5/2 asymptotic competitive ratio for all, arbitrarily large, values of σ. That last result shows that the problem we study can be strictly harder than unit interval coloring. Our main technical contribution is a recursive composition of strategies, which seems essential to prove any lower bound higher than 2.
Cite as

Joanna Chybowska-Sokół, Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Patryk Mikos, and Adam Polak. Online Coloring of Short Intervals. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 52:1-52:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chybowskasokol_et_al:LIPIcs.APPROX/RANDOM.2020.52,
  author =	{Chybowska-Sok\'{o}{\l}, Joanna and Gutowski, Grzegorz and Junosza-Szaniawski, Konstanty and Mikos, Patryk and Polak, Adam},
  title =	{{Online Coloring of Short Intervals}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{52:1--52:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.52},
  URN =		{urn:nbn:de:0030-drops-126550},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.52},
  annote =	{Keywords: Online algorithms, graph coloring, interval graphs}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.46
A Note on Two-Colorability of Nonuniform Hypergraphs

Authors: Lech Duraj, Grzegorz Gutowski, and Jakub Kozik

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

Abstract
For a hypergraph H, let q(H) denote the expected number of monochromatic edges when the color of each vertex in H is sampled uniformly at random from the set of size 2. Let s_{min}(H) denote the minimum size of an edge in H. Erdös asked in 1963 whether there exists an unbounded function g(k) such that any hypergraph H with s_{min}(H) >=slant k and q(H) <=slant g(k) is two colorable. Beck in 1978 answered this question in the affirmative for a function g(k) = Theta(log^* k). We improve this result by showing that, for an absolute constant delta>0, a version of random greedy coloring procedure is likely to find a proper two coloring for any hypergraph H with s_{min}(H) >=slant k and q(H) <=slant delta * log k.
Cite as

Lech Duraj, Grzegorz Gutowski, and Jakub Kozik. A Note on Two-Colorability of Nonuniform Hypergraphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{duraj_et_al:LIPIcs.ICALP.2018.46,
  author =	{Duraj, Lech and Gutowski, Grzegorz and Kozik, Jakub},
  title =	{{A Note on Two-Colorability of Nonuniform Hypergraphs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{46:1--46: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.46},
  URN =		{urn:nbn:de:0030-drops-90505},
  doi =		{10.4230/LIPIcs.ICALP.2018.46},
  annote =	{Keywords: Property B, Nonuniform Hypergraphs, Hypergraph Coloring, Random Greedy Coloring}
}
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