Search Results

Documents authored by Yuditsky, Yelena

Document
DOI: 10.4230/LIPIcs.ESA.2025.67
Compact Representation of Semilinear and Terrain-Like Graphs

Authors: Jean Cardinal and Yelena Yuditsky

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider the existence and construction of biclique covers of graphs, consisting of coverings of their edge sets by complete bipartite graphs. The size of such a cover is the sum of the sizes of the bicliques. Small-size biclique covers of graphs are ubiquitous in computational geometry, and have been shown to be useful compact representations of graphs. We give a brief survey of classical and recent results on biclique covers and their applications, and give new families of graphs having biclique covers of near-linear size. In particular, we show that semilinear graphs, whose edges are defined by linear relations in bounded dimensional space, always have biclique covers of size O(npolylog n). This generalizes many previously known results on special classes of graphs including interval graphs, permutation graphs, and graphs of bounded boxicity, but also new classes such as intersection graphs of L-shapes in the plane. It also directly implies the bounds for Zarankiewicz’s problem derived by Basit, Chernikov, Starchenko, Tao, and Tran (Forum Math. Sigma, 2021). We also consider capped graphs, also known as terrain-like graphs, defined as ordered graphs forbidding a certain ordered pattern on four vertices. Terrain-like graphs contain the induced subgraphs of terrain visibility graphs. We give an elementary proof that these graphs admit biclique partitions of size O(nlog³ n). This provides a simple combinatorial analogue of a classical result from Agarwal, Alon, Aronov, and Suri on polygon visibility graphs (Discrete Comput. Geom. 1994). Finally, we prove that there exists families of unit disk graphs on n vertices that do not admit biclique coverings of size o(n^{4/3}), showing that we are unlikely to improve on Szemerédi-Trotter type incidence bounds for higher-degree semialgebraic graphs.
Cite as

Jean Cardinal and Yelena Yuditsky. Compact Representation of Semilinear and Terrain-Like Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.ESA.2025.67,
  author =	{Cardinal, Jean and Yuditsky, Yelena},
  title =	{{Compact Representation of Semilinear and Terrain-Like Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{67:1--67:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.67},
  URN =		{urn:nbn:de:0030-drops-245359},
  doi =		{10.4230/LIPIcs.ESA.2025.67},
  annote =	{Keywords: Biclique covers, intersection graphs, visibility graphs, Zarankiewicz’s problem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.39
Weak Coloring Numbers of Intersection Graphs

Authors: Zdeněk Dvořák, Jakub Pekárek, Torsten Ueckerdt, and Yelena Yuditsky

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

Abstract
Weak and strong coloring numbers are generalizations of the degeneracy of a graph, where for a positive integer k, we seek a vertex ordering such that every vertex can (weakly respectively strongly) reach in k steps only few vertices that precede it in the ordering. Both notions capture the sparsity of a graph or a graph class, and have interesting applications in structural and algorithmic graph theory. Recently, Dvořák, McCarty, and Norin observed a natural volume-based upper bound for the strong coloring numbers of intersection graphs of well-behaved objects in ℝ^d, such as homothets of a compact convex object, or comparable axis-aligned boxes. In this paper, we prove upper and lower bounds for the k-th weak coloring numbers of these classes of intersection graphs. As a consequence, we describe a natural graph class whose strong coloring numbers are polynomial in k, but the weak coloring numbers are exponential. We also observe a surprising difference in terms of the dependence of the weak coloring numbers on the dimension between touching graphs of balls (single-exponential) and hypercubes (double-exponential).
Cite as

Zdeněk Dvořák, Jakub Pekárek, Torsten Ueckerdt, and Yelena Yuditsky. Weak Coloring Numbers of Intersection Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.SoCG.2022.39,
  author =	{Dvo\v{r}\'{a}k, Zden\v{e}k and Pek\'{a}rek, Jakub and Ueckerdt, Torsten and Yuditsky, Yelena},
  title =	{{Weak Coloring Numbers of Intersection Graphs}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{39:1--39:15},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.39},
  URN =		{urn:nbn:de:0030-drops-160477},
  doi =		{10.4230/LIPIcs.SoCG.2022.39},
  annote =	{Keywords: geometric intersection graphs, weak and strong coloring numbers}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.5
The ε-t-Net Problem

Authors: Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky

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

Abstract
We study a natural generalization of the classical ε-net problem (Haussler - Welzl 1987), which we call the ε-t-net problem: Given a hypergraph on n vertices and parameters t and ε ≥ t/n, find a minimum-sized family S of t-element subsets of vertices such that each hyperedge of size at least ε n contains a set in S. When t=1, this corresponds to the ε-net problem. We prove that any sufficiently large hypergraph with VC-dimension d admits an ε-t-net of size O((1+log t)d/ε log 1/ε). For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of O(1/ε)-sized ε-t-nets. We also present an explicit construction of ε-t-nets (including ε-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of ε-nets (i.e., for t=1), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.
Cite as

Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky. The ε-t-Net Problem. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{alon_et_al:LIPIcs.SoCG.2020.5,
  author =	{Alon, Noga and Jartoux, Bruno and Keller, Chaya and Smorodinsky, Shakhar and Yuditsky, Yelena},
  title =	{{The \epsilon-t-Net Problem}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{5:1--5:15},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.5},
  URN =		{urn:nbn:de:0030-drops-121639},
  doi =		{10.4230/LIPIcs.SoCG.2020.5},
  annote =	{Keywords: epsilon-nets, geometric hypergraphs, VC-dimension, linear union complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.68
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.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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact