Product Structure, Separating Systems, Freeze-Tag Problem, and Planar Multicolor Turan Number

Abstract

This thesis is based on a collection of papers focused on graph theory and computational geometry. The first paper focuses on the Product Structure Theorem for planar graphs, which asserts that any planar graph can be embedded in the strong product of a planar 3-tree, a path, and a 3-cycle. The paper presents a simple linear-time algorithm to find this decomposition for an n-vertex planar graph, improving on the previous O(n log n) time algorithm. In the second paper, the concept of vertex-separating systems is explored, where a separating system is a collection of vertex subsets that is used to distinguish between any two distinct elements of the vertex set. The paper investigates the minimum size of vertex-separating path and tree systems for various types of graphs, including trees, grids, and maximal outerplanar graphs. The third paper tackles the geometric freeze-tag problem, an optimization problem where the goal is to minimize the total wake-up time for a swarm of robots starting with a single active robot. The authors prove a conjecture by Bonichon et al. regarding an upper bound on the wake-up time for robots in convex position and provide an upper bound of 4.63r for robots located in a disk of radius r in the $\ell_2$-norm, improving the best known bound of $5\sqrt{2}r \approx 7.07r$. Finally, the fourth paper addresses the planar rainbow Turan problem, where the objective is to determine the smallest number of maximal planar graphs required on the same set of n vertices to guarantee a rainbow triangle (a triangle formed by edges from three distinct graphs). The paper establishes both upper and lower bounds, showing that a sequence of at least 0.75n planar graphs guarantees a rainbow triangle, and provides an almost linear lower bound using Behrend’s construction for three-term arithmetic progression-free sets. Together, these works contribute to both theoretical and algorithmic advancements in graph decompositions, separating systems, and optimization problems within geometric and graph theoretic settings.