More Like this

1. Unavoidable Patterns in Complete Simple Topological Graphs

   Andrew Suk, Ji Zeng (January 2023, Graph Drawing and Network Visualization: 30th International Symposium, GD 2022, Tokyo, Japan, September 13–16, 2022, Revised Selected Papers)

   Angelini, P. (Ed.)

   We show that every complete n-vertex simple topological graph contains a topological subgraph on at least (logn)1/4−o(1) vertices that is weakly isomorphic to the complete convex geometric graph or the complete twisted graph. This is the first improvement on the bound Ω(log1/8n) obtained in 2003 by Pach, Solymosi, and Tóth. We also show that every complete n-vertex simple topological graph contains a plane path of length at least (logn)1−o(1) . 

   more » « less
2. A Structure Theorem for Pseudo-Segments and Its Applications

   https://doi.org/10.4230/LIPIcs.SoCG.2024.59  

   Fox, Jacob; Pach, János; Suk, Andrew (January 2024, 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
3. Tight paths in convex geometric hypergraphs

   https://doi.org/10.19086/aic.12044  

   Mubayi, Dhruv; Füredi, Zoltán; Verstraëte, Jacques; Kostochka, Alexandr; Jiang, Tao (February 2020, Advances in Combinatorics)

   One of the most intruguing conjectures in extremal graph theory is the conjecture of Erdős and Sós from 1962, which asserts that every $$n$$-vertex graph with more than $$\frac{k-1}{2}n$$ edges contains any $$k$$-edge tree as a subgraph. Kalai proposed a generalization of this conjecture to hypergraphs. To explain the generalization, we need to define the concept of a tight tree in an $$r$$-uniform hypergraph, i.e., a hypergraph where each edge contains $$r$$ vertices. A tight tree is an $$r$$-uniform hypergraph such that there is an ordering $$v_1,\ldots,v_n$$ of its its vertices with the following property: the vertices $$v_1,\ldots,v_r$$ form an edge and for every $i>r$, there is a single edge $$e$$ containing the vertex $$v_i$$ and $r-1$ of the vertices $$v_1,\ldots,v_{i-1}$$, and $$e\setminus\{v_i\}$$ is a subset of one of the edges consisting only of vertices from $$v_1,\ldots,v_{i-1}$$. The conjecture of Kalai asserts that every $$n$$-vertex $$r$$-uniform hypergraph with more than $$\frac{k-1}{r}\binom{n}{r-1}$$ edges contains every $$k$$-edge tight tree as a subhypergraph. The recent breakthrough results on the existence of combinatorial designs by Keevash and by Glock, Kühn, Lo and Osthus show that this conjecture, if true, would be tight for infinitely many values of $$n$$ for every $$r$$ and $$k$$.The article deals with the special case of the conjecture when the sought tight tree is a path, i.e., the edges are the $$r$$-tuples of consecutive vertices in the above ordering. The case $r=2$ is the famous Erdős-Gallai theorem on the existence of paths in graphs. The case $r=3$ and $k=4$ follows from an earlier work of the authors on the conjecture of Kalai. The main result of the article is the first non-trivial upper bound valid for all $$r$$ and $$k$$. The proof is based on techniques developed for a closely related problem where a hypergraph comes with a geometric structure: the vertices are points in the plane in a strictly convex position and the sought path has to zigzag beetwen the vertices. 

   more » « less
4. Simple Topological Drawings of k-Planar Graphs.

   https://doi.org/10.1007/978-3-030-68766-3_31  

   Hoffmann, Michael; Liu, Chih-Hung; Reddy, Meghana M.; Toth, Csaba D. (February 2021, Graph Drawing and Network Visualization)

   null (Ed.)

   Every finite graph admits a simple (topological) drawing, that is, a drawing where every pair of edges intersects in at most one point. However, in combination with other restrictions simple drawings do not universally exist. For instance, k-planar graphs are those graphs that can be drawn so that every edge has at most k crossings (i.e., they admit a k-plane drawing). It is known that for k≤3 , every k-planar graph admits a k-plane simple drawing. But for k≥4 , there exist k-planar graphs that do not admit a k-plane simple drawing. Answering a question by Schaefer, we show that there exists a function Open image in new window such that every k-planar graph admits an f(k)-plane simple drawing, for all Open image in new window. Note that the function f depends on k only and is independent of the size of the graph. Furthermore, we develop an algorithm to show that every 4-planar graph admits an 8-plane simple drawing. 

   more » « less
5. Computing β-Stretch Paths in Drawings of Graphs

   Arkin, E; Darabi, F; Efrat, A; Frank, F; Fulek, R; Kobourov, S; Mitchell, J (October 2020, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT))

   Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1-dimensional simplicial complex. We assume that every edge of G is drawn by f as a curve of constant algebraic complexity, and the ratio of the length of the longest simple path to the the length of the shortest edge is poly(n). In the drawing f, a path P of G, or its image in the drawing π = f(P), is β-stretch if π is a simple (non-self-intersecting) curve, and for every pair of distinct points p ∈ P and q ∈ P , the length of the sub-curve of π connecting f(p) with f(q) is at most β∥f(p) − f(q)∥, where ∥.∥ denotes the Euclidean distance. We introduce and study the β-stretch Path Problem (βSP for short), in which we are given a pair of vertices s and t of G, and we are to decide whether in the given drawing of G there exists a β-stretch path P connecting s and t. We also output P if it exists. The βSP quantifies a notion of “near straightness” for paths in a graph G, motivated by gerrymandering regions in a map, where edges of G represent natural geographical/political boundaries that may be chosen to bound election districts. The notion of a β-stretch path naturally extends to cycles, and the extension gives a measure of how gerrymandered a district is. Furthermore, we show that the extension is closely related to several studied measures of local fatness of geometric shapes. We prove that βSP is strongly NP-complete. We complement this result by giving a quasi-polynomial time algorithm, that for a given ε > 0, β ∈ O(poly(log |V (G)|)), and s, t ∈ V (G), outputs a β-stretch path between s and t, if a (1 − ε)β-stretch path between s and t exists in the drawing. 

   more » « less