标题： 半线性和地形类图的紧凑表示 显示英文标题

标题： Compact Representation of Semilinear and Terrain-like Graphs

摘要： 我们考虑图的\textit{双团覆盖}的存在性和构造，这些图由其边集被完全二部图覆盖组成。这种覆盖的\textit{大小}是各个二部图大小的总和。小规模的二部图覆盖在计算几何中很常见，并已被证明是图的有用紧凑表示。我们简要回顾了关于二部图覆盖及其应用的经典和最新结果，并给出了具有近线性大小二部图覆盖的新图类。特别是，我们证明了半线性图，其边由有界维空间中的线性关系定义，总是具有大小为$O(n\polylog n)$的二部图覆盖。这推广了许多之前已知的特殊图类的结果，包括区间图、排列图和有界箱维度的图，但也包括新的类，如平面中 L 形状的交图。它还直接推导出 Basit、Chernikov、Starchenko、Tao 和 Tran（\textit{论坛 数学。 西格玛}，2021）得出的 Zarankiewicz 问题的界限。我们还考虑了截断图，也称为地形类似图，定义为禁止在四个顶点上具有某种有序模式的有序图。地形类似图包含地形可见图的诱导子图。我们给出了一个简单的证明，这些图具有大小为$O(n\log^3 n)$的二部图划分。这提供了一个经典的 Agarwal、Alon、Aronov 和 Suri 关于多边形可见图的结果（\textit{离散计算几何} 1994）的简单组合类比。 最后，我们证明了存在一些单位圆图族，它们在$n$个顶点上不具有大小为$o(n^{4/3})$的双 clique 覆盖，这表明我们不太可能改进针对高次代数图的 Szemerédi-Trotter 类型的交点界限。 显示英文摘要

摘要： We consider the existence and construction of \textit{biclique covers} of graphs, consisting of coverings of their edge sets by complete bipartite graphs. The \textit{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(n\polylog 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 (\textit{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(n\log^3 n)$. This provides a simple combinatorial analogue of a classical result from Agarwal, Alon, Aronov, and Suri on polygon visibility graphs (\textit{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\'edi-Trotter type incidence bounds for higher-degree semialgebraic graphs.