18 Search Results for "Pach, János"


Volume

LIPIcs, Volume 34

31st International Symposium on Computational Geometry (SoCG 2015)

SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands

Editors: Lars Arge and János Pach

Document
Disjointness Graphs of Short Polygonal Chains

Authors: János Pach, Gábor Tardos, and Géza Tóth

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


Abstract
The disjointness graph of a set system is a graph whose vertices are the sets, two being connected by an edge if and only if they are disjoint. It is known that the disjointness graph G of any system of segments in the plane is χ-bounded, that is, its chromatic number χ(G) is upper bounded by a function of its clique number ω(G). Here we show that this statement does not remain true for systems of polygonal chains of length 2. We also construct systems of polygonal chains of length 3 such that their disjointness graphs have arbitrarily large girth and chromatic number. In the opposite direction, we show that the class of disjointness graphs of (possibly self-intersecting) 2-way infinite polygonal chains of length 3 is χ-bounded: for every such graph G, we have χ(G) ≤ (ω(G))³+ω(G).

Cite as

János Pach, Gábor Tardos, and Géza Tóth. Disjointness Graphs of Short Polygonal Chains. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 56:1-56:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{pach_et_al:LIPIcs.SoCG.2022.56,
  author =	{Pach, J\'{a}nos and Tardos, G\'{a}bor and T\'{o}th, G\'{e}za},
  title =	{{Disjointness Graphs of Short Polygonal Chains}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{56:1--56:12},
  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.56},
  URN =		{urn:nbn:de:0030-drops-160645},
  doi =		{10.4230/LIPIcs.SoCG.2022.56},
  annote =	{Keywords: chi-bounded, disjointness graph}
}
Document
The Density Fingerprint of a Periodic Point Set

Authors: Herbert Edelsbrunner, Teresa Heiss, Vitaliy Kurlin, Philip Smith, and Mathijs Wintraecken

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


Abstract
Modeling a crystal as a periodic point set, we present a fingerprint consisting of density functions that facilitates the efficient search for new materials and material properties. We prove invariance under isometries, continuity, and completeness in the generic case, which are necessary features for the reliable comparison of crystals. The proof of continuity integrates methods from discrete geometry and lattice theory, while the proof of generic completeness combines techniques from geometry with analysis. The fingerprint has a fast algorithm based on Brillouin zones and related inclusion-exclusion formulae. We have implemented the algorithm and describe its application to crystal structure prediction.

Cite as

Herbert Edelsbrunner, Teresa Heiss, Vitaliy Kurlin, Philip Smith, and Mathijs Wintraecken. The Density Fingerprint of a Periodic Point Set. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{edelsbrunner_et_al:LIPIcs.SoCG.2021.32,
  author =	{Edelsbrunner, Herbert and Heiss, Teresa and Kurlin, Vitaliy and Smith, Philip and Wintraecken, Mathijs},
  title =	{{The Density Fingerprint of a Periodic Point Set}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{32:1--32: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.32},
  URN =		{urn:nbn:de:0030-drops-138310},
  doi =		{10.4230/LIPIcs.SoCG.2021.32},
  annote =	{Keywords: Lattices, periodic sets, isometries, Dirichlet-Voronoi domains, Brillouin zones, bottleneck distance, stability, continuity, crystal database}
}
Document
Sunflowers in Set Systems of Bounded Dimension

Authors: Jacob Fox, János Pach, and Andrew Suk

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


Abstract
Given a family F of k-element sets, S₁,…,S_r ∈ F form an r-sunflower if S_i ∩ S_j = S_{i'} ∩ S_{j'} for all i ≠ j and i' ≠ j'. According to a famous conjecture of Erdős and Rado (1960), there is a constant c = c(r) such that if |F| ≥ c^k, then F contains an r-sunflower. We come close to proving this conjecture for families of bounded Vapnik-Chervonenkis dimension, VC-dim(F) ≤ d. In this case, we show that r-sunflowers exist under the slightly stronger assumption |F| ≥ 2^{10k(dr)^{2log^{*} k}}. Here, log^* denotes the iterated logarithm function. We also verify the Erdős-Rado conjecture for families F of bounded Littlestone dimension and for some geometrically defined set systems.

Cite as

Jacob Fox, János Pach, and Andrew Suk. Sunflowers in Set Systems of Bounded Dimension. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.SoCG.2021.37,
  author =	{Fox, Jacob and Pach, J\'{a}nos and Suk, Andrew},
  title =	{{Sunflowers in Set Systems of Bounded Dimension}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{37:1--37:13},
  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.37},
  URN =		{urn:nbn:de:0030-drops-138366},
  doi =		{10.4230/LIPIcs.SoCG.2021.37},
  annote =	{Keywords: Sunflower, VC-dimension, Littlestone dimension, pseudodisks}
}
Document
Bounded VC-Dimension Implies the Schur-Erdős Conjecture

Authors: Jacob Fox, János Pach, and Andrew Suk

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)


Abstract
In 1916, Schur introduced the Ramsey number r(3;m), which is the minimum integer n > 1 such that for any m-coloring of the edges of the complete graph K_n, there is a monochromatic copy of K₃. He showed that r(3;m) ≤ O(m!), and a simple construction demonstrates that r(3;m) ≥ 2^Ω(m). An old conjecture of Erdős states that r(3;m) = 2^Θ(m). In this note, we prove the conjecture for m-colorings with bounded VC-dimension, that is, for m-colorings with the property that the set system induced by the neighborhoods of the vertices with respect to each color class has bounded VC-dimension.

Cite as

Jacob Fox, János Pach, and Andrew Suk. Bounded VC-Dimension Implies the Schur-Erdős Conjecture. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 46:1-46:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.SoCG.2020.46,
  author =	{Fox, Jacob and Pach, J\'{a}nos and Suk, Andrew},
  title =	{{Bounded VC-Dimension Implies the Schur-Erd\H{o}s Conjecture}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{46:1--46:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.46},
  URN =		{urn:nbn:de:0030-drops-122046},
  doi =		{10.4230/LIPIcs.SoCG.2020.46},
  annote =	{Keywords: Ramsey theory, VC-dimension, Multicolor Ramsey numbers}
}
Document
On Geometric Set Cover for Orthants

Authors: Karl Bringmann, Sándor Kisfaludi-Bak, Michał Pilipczuk, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
We study SET COVER for orthants: Given a set of points in a d-dimensional Euclidean space and a set of orthants of the form (-infty,p_1] x ... x (-infty,p_d], select a minimum number of orthants so that every point is contained in at least one selected orthant. This problem draws its motivation from applications in multi-objective optimization problems. While for d=2 the problem can be solved in polynomial time, for d>2 no algorithm is known that avoids the enumeration of all size-k subsets of the input to test whether there is a set cover of size k. Our contribution is a precise understanding of the complexity of this problem in any dimension d >= 3, when k is considered a parameter: - For d=3, we give an algorithm with runtime n^O(sqrt{k}), thus avoiding exhaustive enumeration. - For d=3, we prove a tight lower bound of n^Omega(sqrt{k}) (assuming ETH). - For d >=slant 4, we prove a tight lower bound of n^Omega(k) (assuming ETH). Here n is the size of the set of points plus the size of the set of orthants. The first statement comes as a corollary of a more general result: an algorithm for SET COVER for half-spaces in dimension 3. In particular, we show that given a set of points U in R^3, a set of half-spaces D in R^3, and an integer k, one can decide whether U can be covered by the union of at most k half-spaces from D in time |D|^O(sqrt{k})* |U|^O(1). We also study approximation for SET COVER for orthants. While in dimension 3 a PTAS can be inferred from existing results, we show that in dimension 4 and larger, there is no 1.05-approximation algorithm with runtime f(k)* n^o(k) for any computable f, where k is the optimum.

Cite as

Karl Bringmann, Sándor Kisfaludi-Bak, Michał Pilipczuk, and Erik Jan van Leeuwen. On Geometric Set Cover for Orthants. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ESA.2019.26,
  author =	{Bringmann, Karl and Kisfaludi-Bak, S\'{a}ndor and Pilipczuk, Micha{\l} and van Leeuwen, Erik Jan},
  title =	{{On Geometric Set Cover for Orthants}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.26},
  URN =		{urn:nbn:de:0030-drops-111476},
  doi =		{10.4230/LIPIcs.ESA.2019.26},
  annote =	{Keywords: Set Cover, parameterized complexity, algorithms, Exponential Time Hypothesis}
}
Document
Beyond-Planar Graphs: Combinatorics, Models and Algorithms (Dagstuhl Seminar 19092)

Authors: Seok-Hee Hong, Michael Kaufmann, János Pach, and Csaba D. Tóth

Published in: Dagstuhl Reports, Volume 9, Issue 2 (2019)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19092 "Beyond-Planar Graphs: Combinatorics, Models and Algorithms" which brought together 36 researchers in the areas of graph theory, combinatorics, computational geometry, and graph drawing. This seminar continued the work initiated in Dagstuhl Seminar 16452 "Beyond-Planar Graphs: Algorithmics and Combinatorics" and focused on the exploration of structural properties and the development of algorithms for so-called beyond-planar graphs, i.e., non-planar graphs that admit a drawing with topological constraints such as specific types of crossings, or with some forbidden crossing patterns. The seminar began with four talks about the results of scientific collaborations originating from the previous Dagstuhl seminar. Next we discussed open research problems about beyond planar graphs, such as their combinatorial structures (e.g., book thickness, queue number), their topology (e.g., simultaneous embeddability, gap planarity, quasi-quasiplanarity), their geometric representations (e.g., representations on few segments or arcs), and applications (e.g., manipulation of graph drawings by untangling operations). Six working groups were formed that investigated several of the open research questions. In addition, talks on related subjects and recent conference contributions were presented in the morning opening sessions. Abstracts of all talks and a report from each working group are included in this report.

Cite as

Seok-Hee Hong, Michael Kaufmann, János Pach, and Csaba D. Tóth. Beyond-Planar Graphs: Combinatorics, Models and Algorithms (Dagstuhl Seminar 19092). In Dagstuhl Reports, Volume 9, Issue 2, pp. 123-156, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@Article{hong_et_al:DagRep.9.2.123,
  author =	{Hong, Seok-Hee and Kaufmann, Michael and Pach, J\'{a}nos and T\'{o}th, Csaba D.},
  title =	{{Beyond-Planar Graphs: Combinatorics, Models and Algorithms (Dagstuhl Seminar 19092)}},
  pages =	{123--156},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{2},
  editor =	{Hong, Seok-Hee and Kaufmann, Michael and Pach, J\'{a}nos and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.2.123},
  URN =		{urn:nbn:de:0030-drops-108634},
  doi =		{10.4230/DagRep.9.2.123},
  annote =	{Keywords: combinatorial geometry, geometric algorithms, graph algorithms, graph drawing, graph theory, network visualization}
}
Document
Semi-Algebraic Colorings of Complete Graphs

Authors: Jacob Fox, János Pach, and Andrew Suk

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


Abstract
We consider m-colorings of the edges of a complete graph, where each color class is defined semi-algebraically with bounded complexity. The case m = 2 was first studied by Alon et al., who applied this framework to obtain surprisingly strong Ramsey-type results for intersection graphs of geometric objects and for other graphs arising in computational geometry. Considering larger values of m is relevant, e.g., to problems concerning the number of distinct distances determined by a point set. For p >= 3 and m >= 2, the classical Ramsey number R(p;m) is the smallest positive integer n such that any m-coloring of the edges of K_n, the complete graph on n vertices, contains a monochromatic K_p. It is a longstanding open problem that goes back to Schur (1916) to decide whether R(p;m)=2^{O(m)}, for a fixed p. We prove that this is true if each color class is defined semi-algebraically with bounded complexity, and that the order of magnitude of this bound is tight. Our proof is based on the Cutting Lemma of Chazelle et al., and on a Szemerédi-type regularity lemma for multicolored semi-algebraic graphs, which is of independent interest. The same technique is used to address the semi-algebraic variant of a more general Ramsey-type problem of Erdős and Shelah.

Cite as

Jacob Fox, János Pach, and Andrew Suk. Semi-Algebraic Colorings of Complete Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 36:1-36:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.SoCG.2019.36,
  author =	{Fox, Jacob and Pach, J\'{a}nos and Suk, Andrew},
  title =	{{Semi-Algebraic Colorings of Complete Graphs}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{36:1--36:12},
  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.36},
  URN =		{urn:nbn:de:0030-drops-104401},
  doi =		{10.4230/LIPIcs.SoCG.2019.36},
  annote =	{Keywords: Semi-algebraic graphs, Ramsey theory, regularity lemma}
}
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
A Crossing Lemma for Multigraphs

Authors: János Pach and Géza Tóth

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)


Abstract
Let G be a drawing of a graph with n vertices and e>4n edges, in which no two adjacent edges cross and any pair of independent edges cross at most once. According to the celebrated Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi and Leighton, the number of crossings in G is at least c{e^3 over n^2}, for a suitable constant c>0. In a seminal paper, Székely generalized this result to multigraphs, establishing the lower bound c{e^3 over mn^2}, where m denotes the maximum multiplicity of an edge in G. We get rid of the dependence on m by showing that, as in the original Crossing Lemma, the number of crossings is at least c'{e^3 over n^2} for some c'>0, provided that the "lens" enclosed by every pair of parallel edges in G contains at least one vertex. This settles a conjecture of Bekos, Kaufmann, and Raftopoulou.

Cite as

János Pach and Géza Tóth. A Crossing Lemma for Multigraphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 65:1-65:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{pach_et_al:LIPIcs.SoCG.2018.65,
  author =	{Pach, J\'{a}nos and T\'{o}th, G\'{e}za},
  title =	{{A Crossing Lemma for Multigraphs}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{65:1--65:13},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.65},
  URN =		{urn:nbn:de:0030-drops-87781},
  doi =		{10.4230/LIPIcs.SoCG.2018.65},
  annote =	{Keywords: crossing number, Crossing Lemma, multigraph, separator theorem}
}
Document
Almost All String Graphs are Intersection Graphs of Plane Convex Sets

Authors: János Pach, Bruce Reed, and Yelena Yuditsky

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)


Abstract
A string graph is the intersection graph of a family of continuous arcs in the plane. The intersection graph of a family of plane convex sets is a string graph, but not all string graphs can be obtained in this way. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of almost all string graphs on n vertices can be partitioned into five cliques such that some pair of them is not connected by any edge (n --> infty). We also show that every graph with the above property is an intersection graph of plane convex sets. As a corollary, we obtain that almost all string graphs on n vertices are intersection graphs of plane convex sets.

Cite as

János Pach, Bruce Reed, and Yelena Yuditsky. Almost All String Graphs are Intersection Graphs of Plane Convex Sets. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{pach_et_al:LIPIcs.SoCG.2018.68,
  author =	{Pach, J\'{a}nos and Reed, Bruce and Yuditsky, Yelena},
  title =	{{Almost All String Graphs are Intersection Graphs of Plane Convex Sets}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{68:1--68:14},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.68},
  URN =		{urn:nbn:de:0030-drops-87818},
  doi =		{10.4230/LIPIcs.SoCG.2018.68},
  annote =	{Keywords: String graph, intersection graph, plane convex set}
}
Document
Erdös-Hajnal Conjecture for Graphs with Bounded VC-Dimension

Authors: Jacob Fox, János Pach, and Andrew Suk

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


Abstract
The Vapnik-Chervonenkis dimension (in short, VC-dimension) of a graph is defined as the VC-dimension of the set system induced by the neighborhoods of its vertices. We show that every n-vertex graph with bounded VC-dimension contains a clique or an independent set of size at least e^{(log n)^{1 - o(1)}}. The dependence on the VC-dimension is hidden in the o(1) term. This improves the general lower bound, e^{c sqrt{log n}}, due to Erdos and Hajnal, which is valid in the class of graphs satisfying any fixed nontrivial hereditary property. Our result is almost optimal and nearly matches the celebrated Erdos-Hajnal conjecture, according to which one can always find a clique or an independent set of size at least e^{Omega(log n)}. Our results partially explain why most geometric intersection graphs arising in discrete and computational geometry have exceptionally favorable Ramsey-type properties. Our main tool is a partitioning result found by Lovasz-Szegedy and Alon-Fischer-Newman, which is called the "ultra-strong regularity lemma" for graphs with bounded VC-dimension. We extend this lemma to k-uniform hypergraphs, and prove that the number of parts in the partition can be taken to be (1/epsilon)^{O(d)}, improving the original bound of (1/epsilon)^{O(d^2)} in the graph setting. We show that this bound is tight up to an absolute constant factor in the exponent. Moreover, we give an O(n^k)-time algorithm for finding a partition meeting the requirements in the k-uniform setting.

Cite as

Jacob Fox, János Pach, and Andrew Suk. Erdös-Hajnal Conjecture for Graphs with Bounded VC-Dimension. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.SoCG.2017.43,
  author =	{Fox, Jacob and Pach, J\'{a}nos and Suk, Andrew},
  title =	{{Erd\"{o}s-Hajnal Conjecture for Graphs with Bounded VC-Dimension}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{43:1--43: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.43},
  URN =		{urn:nbn:de:0030-drops-72246},
  doi =		{10.4230/LIPIcs.SoCG.2017.43},
  annote =	{Keywords: VC-dimension, Ramsey theory, regularity lemma}
}
Document
Disjointness Graphs of Segments

Authors: János Pach, Gábor Tardos, and Géza Tóth

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


Abstract
The disjointness graph G=G(S) of a set of segments S in R^d, d>1 is a graph whose vertex set is S and two vertices are connected by an edge if and only if the corresponding segments are disjoint. We prove that the chromatic number of G satisfies chi(G)<=omega(G)^4+omega(G)^3 where omega(G) denotes the clique number of G. It follows, that S has at least cn^{1/5} pairwise intersecting or pairwise disjoint elements. Stronger bounds are established for lines in space, instead of segments. We show that computing omega(G) and chi(G) for disjointness graphs of lines in space are NP-hard tasks. However, we can design efficient algorithms to compute proper colorings of G in which the number of colors satisfies the above upper bounds. One cannot expect similar results for sets of continuous arcs, instead of segments, even in the plane. We construct families of arcs whose disjointness graphs are triangle-free (omega(G)=2), but whose chromatic numbers are arbitrarily large.

Cite as

János Pach, Gábor Tardos, and Géza Tóth. Disjointness Graphs of Segments. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{pach_et_al:LIPIcs.SoCG.2017.59,
  author =	{Pach, J\'{a}nos and Tardos, G\'{a}bor and T\'{o}th, G\'{e}za},
  title =	{{Disjointness Graphs of Segments}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{59:1--59: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.59},
  URN =		{urn:nbn:de:0030-drops-71960},
  doi =		{10.4230/LIPIcs.SoCG.2017.59},
  annote =	{Keywords: disjointness graph, chromatic number, clique number, chi-bounded}
}
Document
Beyond-Planar Graphs: Algorithmics and Combinatorics (Dagstuhl Seminar 16452)

Authors: Sok-Hee Hong, Michael Kaufmann, Stephen G. Kobourov, and János Pach

Published in: Dagstuhl Reports, Volume 6, Issue 11 (2017)


Abstract
This report summarizes Dagstuhl Seminar 16452 "Beyond-Planar Graphs: Algorithmics and Combinatorics'' and documents the talks and discussions. The seminar brought together 29 researchers in the areas of graph theory, combinatorics, computational geometry, and graph drawing. The common interest was in the exploration of structural properties and the development of algorithms for so-called beyond-planar graphs, i.e., non-planar graphs with topological constraints such as specific types of crossings, or with some forbidden crossing patterns. The seminar began with three introductory talks by experts in the different fields. Abstracts of these talks are collected in this report. Next we discussed and grouped together open research problems about beyond planar graphs, such as their combinatorial structures (e.g, thickness, crossing number, coloring), their topology (e.g., string graph representation), their geometric representations (e.g., straight-line drawing, visibility representation, contact representation), and applications (e.g., algorithms for real-world network visualization). Four working groups were formed and a report from each group is included here.

Cite as

Sok-Hee Hong, Michael Kaufmann, Stephen G. Kobourov, and János Pach. Beyond-Planar Graphs: Algorithmics and Combinatorics (Dagstuhl Seminar 16452). In Dagstuhl Reports, Volume 6, Issue 11, pp. 35-62, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@Article{hong_et_al:DagRep.6.11.35,
  author =	{Hong, Sok-Hee and Kaufmann, Michael and Kobourov, Stephen G. and Pach, J\'{a}nos},
  title =	{{Beyond-Planar Graphs: Algorithmics and Combinatorics (Dagstuhl Seminar 16452)}},
  pages =	{35--62},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{6},
  number =	{11},
  editor =	{Hong, Sok-Hee and Kaufmann, Michael and Kobourov, Stephen G. 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/DagRep.6.11.35},
  URN =		{urn:nbn:de:0030-drops-70385},
  doi =		{10.4230/DagRep.6.11.35},
  annote =	{Keywords: graph drawing, graph algorithms, graph theory, geometric algorithms, combinatorial geometry, visualization}
}
Document
A Lower Bound on Opaque Sets

Authors: Akitoshi Kawamura, Sonoko Moriyama, Yota Otachi, and János Pach

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)


Abstract
It is proved that the total length of any set of countably many rectifiable curves, whose union meets all straight lines that intersect the unit square U, is at least 2.00002. This is the first improvement on the lower bound of 2 by Jones in 1964. A similar bound is proved for all convex sets U other than a triangle.

Cite as

Akitoshi Kawamura, Sonoko Moriyama, Yota Otachi, and János Pach. A Lower Bound on Opaque Sets. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 46:1-46:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{kawamura_et_al:LIPIcs.SoCG.2016.46,
  author =	{Kawamura, Akitoshi and Moriyama, Sonoko and Otachi, Yota and Pach, J\'{a}nos},
  title =	{{A Lower Bound on Opaque Sets}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{46:1--46:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.46},
  URN =		{urn:nbn:de:0030-drops-59386},
  doi =		{10.4230/LIPIcs.SoCG.2016.46},
  annote =	{Keywords: barriers; Cauchy-Crofton formula; lower bound; opaque sets}
}
  • Refine by Author
  • 15 Pach, János
  • 4 Fox, Jacob
  • 4 Suk, Andrew
  • 3 Tóth, Géza
  • 2 Arge, Lars
  • Show More...

  • Refine by Classification
  • 3 Mathematics of computing → Combinatoric problems
  • 2 Theory of computation → Computational geometry
  • 1 Mathematics of computing → Graph coloring
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Computational complexity and cryptography

  • Refine by Keyword
  • 3 Ramsey theory
  • 3 VC-dimension
  • 2 chi-bounded
  • 2 chromatic number
  • 2 combinatorial geometry
  • Show More...

  • Refine by Type
  • 17 document
  • 1 volume

  • Refine by Publication Year
  • 4 2019
  • 3 2015
  • 3 2017
  • 2 2016
  • 2 2018
  • 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