9 Search Results for "Walczak, Bartosz"


Document
Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks

Authors: Mikkel Abrahamsen and Bartosz Walczak

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)


Abstract
For smooth convex disks A, i.e., convex compact subsets of the plane with non-empty interior, we classify the classes G^{hom}(A) and G^{sim}(A) of intersection graphs that can be obtained from homothets and similarities of A, respectively. Namely, we prove that G^{hom}(A) = G^{hom}(B) if and only if A and B are affine equivalent, and G^{sim}(A) = G^{sim}(B) if and only if A and B are similar.

Cite as

Mikkel Abrahamsen and Bartosz Walczak. Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2023.2,
  author =	{Abrahamsen, Mikkel and Walczak, Bartosz},
  title =	{{Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{2:1--2:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.2},
  URN =		{urn:nbn:de:0030-drops-178523},
  doi =		{10.4230/LIPIcs.SoCG.2023.2},
  annote =	{Keywords: geometric intersection graph, convex disk, homothet, similarity}
}
Document
A Solution to Ringel’s Circle Problem

Authors: James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, and Bartosz Walczak

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)


Abstract
We construct families of circles in the plane such that their tangency graphs have arbitrarily large girth and chromatic number. This provides a strong negative answer to Ringel’s circle problem (1959). The proof relies on a (multidimensional) version of Gallai’s theorem with polynomial constraints, which we derive from the Hales-Jewett theorem and which may be of independent interest.

Cite as

James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, and Bartosz Walczak. A Solution to Ringel’s Circle Problem. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{davies_et_al:LIPIcs.SoCG.2022.33,
  author =	{Davies, James and Keller, Chaya and Kleist, Linda and Smorodinsky, Shakhar and Walczak, Bartosz},
  title =	{{A Solution to Ringel’s Circle Problem}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{33:1--33:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.33},
  URN =		{urn:nbn:de:0030-drops-160413},
  doi =		{10.4230/LIPIcs.SoCG.2022.33},
  annote =	{Keywords: circle arrangement, chromatic number, Gallai’s theorem, polynomial method}
}
Document
Colouring Polygon Visibility Graphs and Their Generalizations

Authors: James Davies, Tomasz Krawczyk, Rose McCarty, and Bartosz Walczak

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)


Abstract
Curve pseudo-visibility graphs generalize polygon and pseudo-polygon visibility graphs and form a hereditary class of graphs. We prove that every curve pseudo-visibility graph with clique number ω has chromatic number at most 3⋅4^{ω-1}. The proof is carried through in the setting of ordered graphs; we identify two conditions satisfied by every curve pseudo-visibility graph (considered as an ordered graph) and prove that they are sufficient for the claimed bound. The proof is algorithmic: both the clique number and a colouring with the claimed number of colours can be computed in polynomial time.

Cite as

James Davies, Tomasz Krawczyk, Rose McCarty, and Bartosz Walczak. Colouring Polygon Visibility Graphs and Their Generalizations. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{davies_et_al:LIPIcs.SoCG.2021.29,
  author =	{Davies, James and Krawczyk, Tomasz and McCarty, Rose and Walczak, Bartosz},
  title =	{{Colouring Polygon Visibility Graphs and Their Generalizations}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.29},
  URN =		{urn:nbn:de:0030-drops-138281},
  doi =		{10.4230/LIPIcs.SoCG.2021.29},
  annote =	{Keywords: Visibility graphs, \chi-boundedness, pseudoline arrangements, ordered graphs}
}
Document
Vertex Deletion into Bipartite Permutation Graphs

Authors: Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk, Jana Novotná, and Karolina Okrasa

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)


Abstract
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines 𝓁₁ and 𝓁₂, one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given n-vertex graph, whether we can remove at most k vertices to obtain a bipartite permutation graph. This problem is NP-complete by the classical result of Lewis and Yannakakis [John M. Lewis and Mihalis Yannakakis, 1980]. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs. We exploit the structural properties of the shortest hole in a such graph. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time f(k)n^O(1), and also give a polynomial-time 9-approximation algorithm.

Cite as

Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk, Jana Novotná, and Karolina Okrasa. Vertex Deletion into Bipartite Permutation Graphs. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{bozyk_et_al:LIPIcs.IPEC.2020.5,
  author =	{Bo\.{z}yk, {\L}ukasz and Derbisz, Jan and Krawczyk, Tomasz and Novotn\'{a}, Jana and Okrasa, Karolina},
  title =	{{Vertex Deletion into Bipartite Permutation Graphs}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.5},
  URN =		{urn:nbn:de:0030-drops-133087},
  doi =		{10.4230/LIPIcs.IPEC.2020.5},
  annote =	{Keywords: permutation graphs, comparability graphs, partially ordered set, graph modification problems}
}
Document
Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs

Authors: Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, and Bartosz Walczak

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)


Abstract
Let C and D be hereditary graph classes. Consider the following problem: given a graph G in D, find a largest, in terms of the number of vertices, induced subgraph of G that belongs to C. We prove that it can be solved in 2^{o(n)} time, where n is the number of vertices of G, if the following conditions are satisfied: - the graphs in C are sparse, i.e., they have linearly many edges in terms of the number of vertices; - the graphs in D admit balanced separators of size governed by their density, e.g., O(Delta) or O(sqrt{m}), where Delta and m denote the maximum degree and the number of edges, respectively; and - the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph. This leads, for example, to the following corollaries for specific classes C and D: - a largest induced forest in a P_t-free graph can be found in 2^{O~(n^{2/3})} time, for every fixed t; and - a largest induced planar graph in a string graph can be found in 2^{O~(n^{3/4})} time.

Cite as

Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, and Bartosz Walczak. Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 23:1-23:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{novotna_et_al:LIPIcs.IPEC.2019.23,
  author =	{Novotn\'{a}, Jana and Okrasa, Karolina and Pilipczuk, Micha{\l} and Rz\k{a}\.{z}ewski, Pawe{\l} and van Leeuwen, Erik Jan and Walczak, Bartosz},
  title =	{{Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{23:1--23:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.23},
  URN =		{urn:nbn:de:0030-drops-114845},
  doi =		{10.4230/LIPIcs.IPEC.2019.23},
  annote =	{Keywords: subexponential algorithm, feedback vertex set, P\underlinet-free graphs, string graphs}
}
Document
On the Chromatic Number of Disjointness Graphs of Curves

Authors: János Pach and István Tomon

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


Abstract
Let omega(G) and chi(G) denote the clique number and chromatic number of a graph G, respectively. The disjointness graph of a family of curves (continuous arcs in the plane) is the graph whose vertices correspond to the curves and in which two vertices are joined by an edge if and only if the corresponding curves are disjoint. A curve is called x-monotone if every vertical line intersects it in at most one point. An x-monotone curve is grounded if its left endpoint lies on the y-axis. We prove that if G is the disjointness graph of a family of grounded x-monotone curves such that omega(G)=k, then chi(G)<= binom{k+1}{2}. If we only require that every curve is x-monotone and intersects the y-axis, then we have chi(G)<= k+1/2 binom{k+2}{3}. Both of these bounds are best possible. The construction showing the tightness of the last result settles a 25 years old problem: it yields that there exist K_k-free disjointness graphs of x-monotone curves such that any proper coloring of them uses at least Omega(k^{4}) colors. This matches the upper bound up to a constant factor.

Cite as

János Pach and István Tomon. On the Chromatic Number of Disjointness Graphs of Curves. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{pach_et_al:LIPIcs.SoCG.2019.54,
  author =	{Pach, J\'{a}nos and Tomon, Istv\'{a}n},
  title =	{{On the Chromatic Number of Disjointness Graphs of Curves}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{54:1--54: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.54},
  URN =		{urn:nbn:de:0030-drops-104582},
  doi =		{10.4230/LIPIcs.SoCG.2019.54},
  annote =	{Keywords: string graph, chromatic number, intersection graph}
}
Document
Coloring Curves That Cross a Fixed Curve

Authors: Alexandre Rok and Bartosz Walczak

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)


Abstract
We prove that for every integer t greater than or equal to 1, the class of intersection graphs of curves in the plane each of which crosses a fixed curve in at least one and at most t points is chi-bounded. This is essentially the strongest chi-boundedness result one can get for this kind of graph classes. As a corollary, we prove that for any fixed integers k > 1 and t > 0, every k-quasi-planar topological graph on n vertices with any two edges crossing at most t times has O(n log n) edges.

Cite as

Alexandre Rok and Bartosz Walczak. Coloring Curves That Cross a Fixed Curve. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{rok_et_al:LIPIcs.SoCG.2017.56,
  author =	{Rok, Alexandre and Walczak, Bartosz},
  title =	{{Coloring Curves That Cross a Fixed Curve}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{56:1--56:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.56},
  URN =		{urn:nbn:de:0030-drops-71788},
  doi =		{10.4230/LIPIcs.SoCG.2017.56},
  annote =	{Keywords: String graphs, chi-boundedness, k-quasi-planar graphs}
}
Document
Outer Common Tangents and Nesting of Convex Hulls in Linear Time and Constant Workspace

Authors: Mikkel Abrahamsen and Bartosz Walczak

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)


Abstract
We describe the first algorithm to compute the outer common tangents of two disjoint simple polygons using linear time and only constant workspace. A tangent of a polygon is a line touching the polygon such that all of the polygon lies on the same side of the line. An outer common tangent of two polygons is a tangent of both polygons such that the polygons lie on the same side of the tangent. Each polygon is given as a read-only array of its corners in cyclic order. The algorithm detects if an outer common tangent does not exist, which is the case if and only if the convex hull of one of the polygons is contained in the convex hull of the other. Otherwise, two corners defining an outer common tangent are returned.

Cite as

Mikkel Abrahamsen and Bartosz Walczak. Outer Common Tangents and Nesting of Convex Hulls in Linear Time and Constant Workspace. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.ESA.2016.4,
  author =	{Abrahamsen, Mikkel and Walczak, Bartosz},
  title =	{{Outer Common Tangents and Nesting of Convex Hulls in Linear Time and Constant Workspace}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.4},
  URN =		{urn:nbn:de:0030-drops-63465},
  doi =		{10.4230/LIPIcs.ESA.2016.4},
  annote =	{Keywords: simple polygon, common tangent, optimal algorithm, constant workspace}
}
Document
On the Beer Index of Convexity and Its Variants

Authors: Martin Balko, Vít Jelínek, Pavel Valtr, and Bartosz Walczak

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)


Abstract
Let S be a subset of R^d with finite positive Lebesgue measure. The Beer index of convexity b(S) of S is the probability that two points of S chosen uniformly independently at random see each other in S. The convexity ratio c(S) of S is the Lebesgue measure of the largest convex subset of S divided by the Lebesgue measure of S. We investigate a relationship between these two natural measures of convexity of S. We show that every subset S of the plane with simply connected components satisfies b(S) <= alpha c(S) for an absolute constant alpha, provided b(S) is defined. This implies an affirmative answer to the conjecture of Cabello et al. asserting that this estimate holds for simple polygons. We also consider higher-order generalizations of b(S). For 1 <= k <= d, the k-index of convexity b_k(S) of a subset S of R^d is the probability that the convex hull of a (k+1)-tuple of points chosen uniformly independently at random from S is contained in S. We show that for every d >= 2 there is a constant beta(d) > 0 such that every subset S of R^d satisfies b_d(S) <= beta c(S), provided b_d(S) exists. We provide an almost matching lower bound by showing that there is a constant gamma(d) > 0 such that for every epsilon from (0,1] there is a subset S of R^d of Lebesgue measure one satisfying c(S) <= epsilon and b_d(S) >= (gamma epsilon)/log_2(1/epsilon) >= (gamma c(S))/log_2(1/c(S)).

Cite as

Martin Balko, Vít Jelínek, Pavel Valtr, and Bartosz Walczak. On the Beer Index of Convexity and Its Variants. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 406-420, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{balko_et_al:LIPIcs.SOCG.2015.406,
  author =	{Balko, Martin and Jel{\'\i}nek, V{\'\i}t and Valtr, Pavel and Walczak, Bartosz},
  title =	{{On the Beer Index of Convexity and Its Variants}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{406--420},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.406},
  URN =		{urn:nbn:de:0030-drops-51229},
  doi =		{10.4230/LIPIcs.SOCG.2015.406},
  annote =	{Keywords: Beer index of convexity, convexity ratio, convexity measure, visibility}
}
  • Refine by Author
  • 7 Walczak, Bartosz
  • 2 Abrahamsen, Mikkel
  • 2 Davies, James
  • 2 Krawczyk, Tomasz
  • 2 Novotná, Jana
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Computational geometry
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 2 chromatic number
  • 1 Beer index of convexity
  • 1 Gallai’s theorem
  • 1 P_t-free graphs
  • 1 String graphs
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 2 2019
  • 1 2015
  • 1 2016
  • 1 2017
  • 1 2020
  • Show More...

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