skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Enumeration of Intersection Graphs of x-Monotone Curves
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^Ω(n^{4/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 2^O(n^{3/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.  more » « less
Award ID(s):
2246847
PAR ID:
10612934
Author(s) / Creator(s):
; ;
Editor(s):
Felsner, Stefan; Klein, Karsten
Publisher / Repository:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Date Published:
Volume:
320
ISSN:
1868-8969
ISBN:
978-3-95977-343-0
Page Range / eLocation ID:
4:1-4:12
Subject(s) / Keyword(s):
Enumeration intersection graphs pseudo-segments x-monotone Mathematics of computing → Combinatorics
Format(s):
Medium: X Size: 12 pages; 669293 bytes Other: application/pdf
Size(s):
12 pages 669293 bytes
Right(s):
Creative Commons Attribution 4.0 International license; info:eu-repo/semantics/openAccess
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Mulzer, Wolfgang; Phillips, Jeff M (Ed.)
    We prove a far-reaching strengthening of Szemerédi’s regularity lemma for intersection graphs of pseudo-segments. It shows that the vertex set of such graphs can be partitioned into a bounded number of parts of roughly the same size such that almost all of the bipartite graphs between pairs of parts are complete or empty. We use this to get an improved bound on disjoint edges in simple topological graphs, showing that every n-vertex simple topological graph with no k pairwise disjoint edges has at most n(log n)^O(log k) edges. 
    more » « less
  2. ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Mulzer, Wolfgang; Phillips, Jeff M (Ed.)
    Finding the diameter of a graph in general cannot be done in truly subquadratic assuming the Strong Exponential Time Hypothesis (SETH), even when the underlying graph is unweighted and sparse. When restricting to concrete classes of graphs and assuming SETH, planar graphs and minor-free graphs admit truly subquadratic algorithms, while geometric intersection graphs of unit balls, congruent equilateral triangles, and unit segments do not. Unit-disk graphs is one of the major open cases where the complexity of diameter computation remains unknown. More generally, it is conjectured that a truly subquadratic time algorithm exists for pseudo-disk graphs where each pair of objects has at most two intersections on the boundary. In this paper, we show a truly-subquadratic algorithm of running time O^~(n^{2-1/18}), for finding the diameter in a unit-disk graph, whose output differs from the optimal solution by at most 2. This is the first algorithm that provides an additive guarantee in distortion, independent of the size or the diameter of the graph. Our algorithm requires two important technical elements. First, we show that for the intersection graph of pseudo-disks, the graph VC-dimension - either of k-hop balls or the distance encoding vectors - is 4. This contrasts to the VC dimension of the pseudo-disks themselves as geometric ranges (which is known to be 3). Second, we introduce a clique-based r-clustering for geometric intersection graphs, which is an analog of the r-division construction for planar graphs. We also showcase the new techniques by establishing new results for distance oracles for unit-disk graphs with subquadratic storage and O(1) query time. The results naturally extend to unit L₁ or L_∞-disks and fat pseudo-disks of similar size. Last, if the pseudo-disks additionally have bounded ply, we have a truly subquadratic algorithm to find the exact diameter. 
    more » « less
  3. ; ; ; ; ; (, Proceedings of the ACM on Management of Data)
    In this paper, we consider two fundamental cut approximation problems on large graphs. We prove new lower bounds for both problems that are optimal up to logarithmic factors. The first problem is approximating cuts in balanced directed graphs. In this problem, we want to build a data structure that can provide (1 ± ε)-approximation of cut values on a graph with n vertices. For arbitrary directed graphs, such a data structure requires Ω(n2) bits even for constant ε. To circumvent this, recent works study β-balanced graphs, meaning that for every directed cut, the total weight of edges in one direction is at most β times the total weight in the other direction. We consider the for-each model, where the goal is to approximate each cut with constant probability, and the for-all model, where all cuts must be preserved simultaneously. We improve the previous Ømega(n √β/ε) lower bound in the for-each model to ~Ω (n √β /ε) and we improve the previous Ω(n β/ε) lower bound in the for-all model to Ω(n β/ε2). This resolves the main open questions of (Cen et al., ICALP, 2021). The second problem is approximating the global minimum cut in a local query model, where we can only access the graph via degree, edge, and adjacency queries. We prove an ΩL(min m, m/ε2k R) lower bound for this problem, which improves the previous ΩL(m/k R) lower bound, where m is the number of edges, k is the minimum cut size, and we seek a (1+ε)-approximation. In addition, we show that existing upper bounds with minor modifications match our lower bound up to logarithmic factors. 
    more » « less
  4. ; ; ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Aichholzer, Oswin; Wang, Haitao (Ed.)
    We present new results on 2- and 3-hop spanners for geometric intersection graphs. These include improved upper and lower bounds for 2- and 3-hop spanners for many geometric intersection graphs in ℝ^d. For example, we show that the intersection graph of n balls in ℝ^d admits a 2-hop spanner of size O^*(n^{3/2 - 1/(2(2⌊d/2⌋ + 1))}) and the intersection graph of n fat axis-parallel boxes in ℝ^d admits a 2-hop spanner of size O(n log^{d+1}n). Furthermore, we show that the intersection graph of general semi-algebraic objects in ℝ^d admits a 3-hop spanner of size O^*(n^{3/2 - 1/(2(2D-1))}), where D is a parameter associated with the description complexity of the objects. For such families (or more specifically, for tetrahedra in ℝ³), we provide a lower bound of Ω(n^{4/3}). For 3-hop and axis-parallel boxes in ℝ^d, we provide the upper bound O(n log ^{d-1}n) and lower bound Ω(n ({log n}/{log log n})^{d-2}). 
    more » « less
  5. ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Mulzer, Wolfgang; Phillips, Jeff M (Ed.)
    Let d be a (well-behaved) shortest-path metric defined on a path-connected subset of ℝ² and let 𝒟 = {D_1,…,D_n} be a set of geodesic disks with respect to the metric d. We prove that 𝒢^×(𝒟), the intersection graph of the disks in 𝒟, has a clique-based separator consisting of O(n^{3/4+ε}) cliques. This significantly extends the class of objects whose intersection graphs have small clique-based separators. Our clique-based separator yields an algorithm for q-Coloring that runs in time 2^O(n^{3/4+ε}), assuming the boundaries of the disks D_i can be computed in polynomial time. We also use our clique-based separator to obtain a simple, efficient, and almost exact distance oracle for intersection graphs of geodesic disks. Our distance oracle uses O(n^{7/4+ε}) storage and can report the hop distance between any two nodes in 𝒢^×(𝒟) in O(n^{3/4+ε}) time, up to an additive error of one. So far, distance oracles with an additive error of one that use subquadratic storage and sublinear query time were not known for such general graph classes. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email