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{k1}{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 anmore »
Universal Geometric Graphs
We introduce and study the problem of constructing geometric graphs that have few vertices and edges and that are universal for planar graphs or for some subclass of planar graphs; a geometric graph is universal for a class H of planar graphs if it contains an embedding, i.e., a crossingfree drawing, of every graph in H .
Our main result is that there exists a geometric graph with n vertices and O(nlogn) edges that is universal for nvertex forests; this extends to the geometric setting a wellknown graphtheoretic result by Chung and Graham, which states that there exists an nvertex graph with O(nlogn) edges that contains every nvertex forest as a subgraph. Our O(nlogn) bound on the number of edges is asymptotically optimal.
We also prove that, for every h>0 , every nvertex convex geometric graph that is universal for the class of the nvertex outerplanar graphs has Ωh(n2−1/h) edges; this almost matches the trivial O(n2) upper bound given by the nvertex complete convex geometric graph.
Finally, we prove that there is an nvertex convex geometric graph with n vertices and O(nlogn) edges that is universal for nvertex caterpillars.
 Award ID(s):
 1800734
 Publication Date:
 NSFPAR ID:
 10253559
 Journal Name:
 GraphTheoretic Concepts in Computer Science (WG 2020)
 Volume:
 12301
 Sponsoring Org:
 National Science Foundation
More Like this


In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NPhard and hard to approximate within a factor of n1−ε for any ε > 0. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In Hfree graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NPhardmore »

We present the first algorithm to morph graphs on the torus. Given two isotopic essentially 3connected embeddings of the same graph on the Euclidean flat torus, where the edges in both drawings are geodesics, our algorithm computes a continuous deformation from one drawing to the other, such that all edges are geodesics at all times. Previously even the existence of such a morph was not known. Our algorithm runs in O(n1+ω/2) time, where ω is the matrix multiplication exponent, and the computed morph consists of O(n) parallel linear morphing steps. Existing techniques for morphing planar straightline graphs do not immediatelymore »

For integers $n\ge 0$, an iterated triangulation $\mathrm{Tr}(n)$ is defined recursively as follows: $\mathrm{Tr}(0)$ is the plane triangulation on three vertices and, for $n\ge 1$, $\mathrm{Tr}(n)$ is the plane triangulation obtained from the plane triangulation $\mathrm{Tr}(n1)$ by, for each inner face $F$ of $\mathrm{Tr}(n1)$, adding inside $F$ a new vertex and three edges joining this new vertex to the three vertices incident with $F$. In this paper, we show that there exists a 2edgecoloring of $\mathrm{Tr}(n)$ such that $\mathrm{Tr}(n)$ contains no monochromatic copy of the cycle $C_k$ for any $k\ge 5$. As a consequence, the answer to one of twomore »

Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1dimensional 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 (nonselfintersecting) curve, and for every pair of distinct points p ∈ P and qmore »