Flips & Partitions in Geometric Graphs

Abstract

This thesis investigates two topics related to fundamental problems in combinatorial geometry. The first being related to plane graphs, one of the most widely studied themes in various disciplines related to graph drawing. The second part is concerned with reconfiguraton problems, a fundamental field with increasing popularity.

Edge partitions of complete geometric graphs. The first part of this thesis is concerned with a well-known question posed by Bose, Hurtado, Rivera-Campo, and Wood, who asked whether the edges of every complete geometric graph Kn on an even number of vertices can be partitioned into plane spanning trees. In other words, they asked whether the edges of Kn can be colored in a way such that every color class forms a plane spanning tree. For the special cases that the underlying vertex set is in convex or regular wheel position, a positive answer is known. However, we prove that the statement is not true in general. Even for partitions into arbitrary plane subgraphs instead of spanning trees we provide a negative answer. Our constructions are based on bumpy wheel sets and we give a full characterization which bumpy wheels can be partitioned and which cannot. Additionaly, we provide a characterization for arbitrary wheel sets to admit a partition into plane \emph{double stars} and give a sufficient condition for plane spanning trees.

Finally, we investigate the problem in the broader setting of beyond-planar subgraphs. More precisely, we derive bounds on the number of colors necessary and sufficient to partition a complete geometric graph into k-plane and k-quasi-plane subgraphs. Along the way, we also study the well-known crossing lemma and derive an improvement when restricting to the special case of convex geometric graphs.

Flip graphs. The second part of this thesis is concerned with reconfiguration problems. A natural way to provide structure for a reconfiguration problem is by studying the so-called flip graph, which is defined on a ground set X of objects and a corresponding (local) flip operation. More precisely, the flip graph on X under a given flip operation has a vertex for every element in X and two vertices are adjacent if and only if the corresponding objects differ by a single flip. For a given ground set and flip operation, an important property one is usually interested in, is whether the flip graph is connected. In the affirmative, more refined questions concerning the diameter, the degree of connectivity, or Hamiltonicity are of interest. We study the following three reconfiguration problems:

Flipping plane spanning paths. For a given point set S ⊂ R2 in general position, the ground set X consists of all plane straight-line paths with vertex set S. The flip operation exchanges a single pair of (potentially crossing) edges. We prove connectedness of the flip graph if the underlying point set S is in wheel position or generalized double circle position. Furthermore, we prove that it suffices to show flip-connectivity for certain subgraphs where the starting edge is fixed.

Compatible trees. For a given simple drawing D of the complete graph Kn, the ground set X consists of all subdrawings of D that are plane spanning trees. The flip operation exchanges a set of non-crossing edges. We prove connectedness of the flip graph for special classes of drawings, namely cylindrical, monotone, and strongly c-monotone drawings. Furthermore, we prove connectedness of certain subgraphs, corresponding to some classes of graphs, namely stars, double stars, and twin stars.

Flipping pseudocircles. An arrangement of pseudocircles is a finite collection of simple closed curves in the plane such that every pair of curves is either disjoint or intersects in two crossing points. We prove that triangle flips induce a connected flip graph on intersecting arrangements, i.e., on arrangements where every pair of pseudocircles intersects. As an intermediate result we also show flip-connectivity on cylindrical intersecting arrangements, i.e., arrangements where a single point stabs the interior of every pseudocircle. Moreover, we obtain that the diameter of both flip graphs is cubic in the number of pseudocircles.