×

Thirty essays on geometric graph theory. (English) Zbl 1272.05124

Pach, János (ed.), Thirty essays on geometric graph theory. Berlin: Springer (ISBN 978-1-4614-0109-4/hbk; 978-1-4614-0110-0/ebook). 31-48 (2013).
Summary: This paper studies problems related to visibility among points in the plane. A point \(x\) blocks two points \(v\) and \(w\) if \(x\) is in the interior of the line segment \(\overline{vw}\). A set of points \(P\) is \(k\)-blocked if each point in \(P\) is assigned one of \(k\) colors, such that distinct points \(v, w \in P\) are assigned the same color if and only if some other point in \(P\) blocks \(v\) and \(w\). The focus of this paper is the conjecture that each \(k\)-blocked set has bounded size (as a function of \(k\)). Results in the literature imply that every 2-blocked set has at most 3 points, and every 3-blocked set has at most 6 points. We prove that every 4-blocked set has at most 12 points, and that this bound is tight. In fact, we characterize all sets \(\{{n}_{1},{n}_{2},{n}_{3},{n}_{4}\}\) such that some 4-blocked set has exactly \(n_i\) points in the \(i\)th color class. Among other results, for infinitely many values of \(k\), we construct \(k\)-blocked sets with \(k^{1. 79\dots}\) points.
For the entire collection see [Zbl 1256.05002].

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv