DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.15

High Beer Index Implies Big Hollow Triangles

Authors: Arun Kumar Das, Vít Jelínek, Jan Kynčl, Martin Pergel, Felix Schröder, Peter Stumpf, and Pavel Valtr

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract

The visibility graph of a set S ⊆ ℝ² is the graph whose vertices are the points of S, with two points x,y connected by an edge if and only if they see each other in S, that is, if the segment xy is contained in S. The edge density of this graph is known as the Beer index of S. Previously, it has been shown that a simply connected set S ⊆ ℝ² of unit Lebesgue measure with Beer index β > 0 contains a convex subset of measure Ω(β); in particular, for visibility graphs of simply connected sets, a positive edge density β > 0 implies the existence of a clique containing an Ω(β)-fraction of all vertices. The simple-connectivity assumption cannot be omitted, as there are non-simply-connected sets with Beer index 1 and no convex subset of positive measure. Nevertheless, in this paper, we extend the above result to non-simply-connected sets, by showing that a visibility graph with large edge density contains a triangle with large convex hull. More precisely, we show that a set S ⊆ ℝ² of unit Lebesgue measure with Beer index β > 0 contains three pairwise visible points whose convex hull has measure Ω(β⁹). If in addition S is an open domain with K holes, then S contains three pairwise visible points with convex hull of measure Ω(β/K) as well as a convex subset of measure Ω(β/K²).

Cite as

Arun Kumar Das, Vít Jelínek, Jan Kynčl, Martin Pergel, Felix Schröder, Peter Stumpf, and Pavel Valtr. High Beer Index Implies Big Hollow Triangles. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.WG.2026.15,
  author =	{Das, Arun Kumar and Jel{\'\i}nek, V{\'\i}t and Kyn\v{c}l, Jan and Pergel, Martin and Schr\"{o}der, Felix and Stumpf, Peter and Valtr, Pavel},
  title =	{{High Beer Index Implies Big Hollow Triangles}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.15},
  URN =		{urn:nbn:de:0030-drops-261813},
  doi =		{10.4230/LIPIcs.WG.2026.15},
  annote =	{Keywords: convexity, Beer index, visibility graph}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.23

Precoloring Extension with Demands on Paths

Authors: Arun Kumar Das, Michal Opler, and Tomáš Valla

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

Let G be a graph with a set of precolored vertices, and let us be given an integer distance parameter d and a set of integer demands d₁,… ,d_c. The Distance Precoloring Extension with Demands (DPED) problem is to compute a vertex c-coloring of G such that the following three conditions hold: (i) the resulting coloring respects the colors of the precolored vertices, (ii) the distance of two vertices of the same color is at least d, and (iii) the number of vertices colored by color i is exactly d_i. This problem is motivated by a program scheduling in commercial broadcast channels with constraints on content repetition and placement, which leads precisely to the DPED problem for paths. In this paper, we study DPED on paths and present a polynomial time exact algorithm when precolored vertices are restricted to the two ends of the path and devise an approximation algorithm for DPED with an additive approximation factor polynomially bounded by d and the number of precolored vertices. Then, we prove that the Distance Precoloring Extension problem on paths, a less restrictive version of DPED without the demand constraints, and then DPED itself, is NP-complete. Motivated by this result, we further study the parameterized complexity of DPED on paths. We establish that the DPED problem on paths is W[1]-hard when parameterized by the number of colors and the distance. On the positive side, we devise a fixed parameter tractable (FPT) algorithm for DPED on paths when the number of colors, the distance, and the number of precolored vertices are considered as the parameters. Moreover, we prove that Distance Precoloring Extension is FPT parameterized by the distance. As a byproduct, we also obtain several results for the Distance List Coloring problem on paths.

Cite as

Arun Kumar Das, Michal Opler, and Tomáš Valla. Precoloring Extension with Demands on Paths. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.ISAAC.2025.23,
  author =	{Das, Arun Kumar and Opler, Michal and Valla, Tom\'{a}\v{s}},
  title =	{{Precoloring Extension with Demands on Paths}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.23},
  URN =		{urn:nbn:de:0030-drops-249319},
  doi =		{10.4230/LIPIcs.ISAAC.2025.23},
  annote =	{Keywords: precoloring extension, distance coloring, FPT, approximation algorithms}
}

Search Results

Documents authored by Das, Arun Kumar

High Beer Index Implies Big Hollow Triangles

Abstract

Cite as

Precoloring Extension with Demands on Paths

Abstract

Cite as

Thanks for your feedback!

Could not send message