Miniworkshop on Combinatorial Geometry (CG Week'18)

Abstract: We study exchange operations on noncrossing spanning trees on a set S of n points in the plane in general position. An exchange graph is associated to each operation, whose vertex set is the set T(S) of noncrossing straight-line spanning trees on S, and two vertices are adjacent iff the corresponding spanning trees are related by an operation. Several operations have been introduced in prior work (e.g., exchange, compatible exchange, edge rotation, and edge slide), they all induce connected exchange graphs. We derive new upper and lower bounds on the maximum diameter of the exchange graphs in terms of n. Further, we show that the crossing pattern of the edges of the complete graph on S can be reconstructed from the compatible exchange graph of noncrossing trees, extending a recent result by Keller and Perles. (Joint work with Christopher Lonner, Torrie Nichols, Marcos Oropeza, Alexander Pilz, and Ahad N. Zehmakan.)

Abstract: Topological drawings are natural representations of graphs in the plane, where vertices are represented by points, and edges by curves connecting the points. We consider a natural class of simple topological drawings of complete bipartite graphs, in which we require that one side of the vertex set bipartition lies on the outer boundary of the drawing. We investigate the combinatorics of such drawings. For this purpose, we define combinatorial encodings of the drawings by enumerating the distinct drawings of subgraphs isomorphic to K2,2 and K3,2, and investigate the constraints they must satisfy. We prove that a drawing of Kk,n exists if and only if some simple local conditions are satisfied by the encodings. This directly yields a polynomial-time algorithm for deciding the existence of such a drawing given the encoding. Joint work with Stefan Felsner (TU Berlin).

Abstract: A Z_2-embedding of a graph G on a surface M is a drawing of G on M in which every pair of non-adjacent edges of G cross an even number of times. A classical result of Hanani and Tutte states that only planar graphs admit Z_2-embeddings in the plane. This result and its variants found many applications, most notably in fast embeddability testing of graphs, and extremal and coloring problems on geometrically defined hypergraphs. We will present some recent developments in the study of Z_2-embeddings on higher genus surfaces, and discuss some newly discovered connections between Z_2-embeddings and tournaments, i.e., directed graphs obtained by assigning a direction to each edge in a complete graph. Some parts of the talk are based on joint works with Jan Kyncl.

Abstract: Given a graph $G=(V,E)$ and a fixed integer $k >1$, a coloring of the vertices of $G$ is called k-Conflict-Free (kCF in short) if for any vertex $v$ there exists at least one color that is assigned to at least one and at most $k$ of its neighbors. (there are two versions of the notion of neighborhood: open where it is the set $N(v)$ of all neighbors of $v$ or closed which is ${v} \cup N(v)$. For $k=1$ such colorings have been studied extensively. In particular by J. Pach, G. Tardos, by P. Cheilaris, by Z. Abel, V. Alvarez, E.. Demaine, S. Fekete, A. Gour, A. Hesterberg, P. Keldenich, C. Scheffer and by R. Glebov, T. Szabo and G. Tardos for general graphs. In this talk we focus on string graphs. That is, intersection graphs of simple Jordan curves in the plane.

Abstract: Let $p_1,\ldots,p_n$ be $n$ distinct points in the plane, and assume that the minimum inter-point distance occurs $s_{\min}$ times, while the maximum inter-point distance occurs $s_{\max}$ times. It is shown that $s_{\min} s_{\max} \leq \frac98 n^2 +O(n)$; this settles a conjecture of Erdős and Pach (1990).

Abstract: In the talk, we discuss the solution of a problem of R. Nandakumar by proving that there is no tiling of the plane with pairwise noncongruent triangles of equal area and equal perimeter. One of the proof ingredients is to show that any tiling of a convex polygon with more than three sides with finitely many triangles contains a pair of triangles that share a full side. Joint work with János Pach and Gábor Tardos.

Abstract: There are triangle-free geometric intersection graphs in the plane with n vertices and with chromatic number Θ(log log n), and essentially only one construction is known to achieve this bound. Is it optimal? I will discuss some recent progress on this question. In particular, I will show a matching upper bound of O(log log n) for triangle-free intersection graphs of L-figures, and I will discuss ongoing work aimed at generalizing this upper bound to other geometric shapes (e.g. segments).