Enumeration of Intersection Graphs of x-Monotone Curves

Fox, J. and Pach, János and Suk, A. (2024) Enumeration of Intersection Graphs of x-Monotone Curves. In: Leibniz International Proceedings in Informatics, LIPIcs. Leibniz International Proceedings in Informatics, LIPIcs (320). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 4. ISBN 9783959773430

Preview

Text 2405.20547v1.pdf Download (202kB) | Preview

Abstract

A curve in the plane is x-monotone if every vertical line intersects it at most once. A family of curves are called pseudo-segments if every pair of them have at most one point in common. We construct 2Ω(n4/3) families, each consisting of n labelled x-monotone pseudo-segments such that their intersection graphs are different. On the other hand, we show that the number of such intersection graphs is at most 2O(n3/2-ϵ), where ϵ > 0 is a suitable constant. Our proof uses an upper bound on the number of set systems of size m on a ground set of size n, with VC-dimension at most d. Much better upper bounds are obtained if we only count bipartite intersection graphs, or, in general, intersection graphs with bounded chromatic number. © Jacob Fox, János Pach, and Andrew Suk.

Actions (login required)

Edit Item