CSUN Algebra, Number Theory, and Discrete Mathematics Seminar

A flip is a local operation on a triangulation (maximal planar graph) that switches the diagonal of a $4$-cycle. The flip graph is a graph whose vertices are all triangulations on n vertices and two triangulations are adjacent if they differ by exactly one flip. These graphs have been studied in various settings and have proven to be a very useful and versatile tool to analyze the structure of triangulations, both combinatorially and algorithmically.

In this talk I will present recently improved bounds concerning the combinatorial flip graph, where triangulations are considered to be abstract graphs (rather than, for instance, geometric realizations on a concrete point set). Specifically we show that from every triangulation on $n\ge 6$ vertices we can reach a Hamiltonian triangulation by a sequence of less than $n∕2$ flips. An interesting bit about this bound is that it was known that about $3n∕5$ flips are always sufficient and sometimes necessary to reach a $4$-connected triangulation (which by Tutte’s/Whitney’s Theorem is Hamiltonian). As a byproduct we improve the upper bound on the diameter of the flip graph from $\sim 5.2n$ to $\sim 5n$. Finally, I will discuss an application of our result to a graph drawing problem, showing that every planar graph on $n$ vertices admits an arc diagram with less than $n∕2$ biarcs, that is, after subdividing less than $n∕2$ (of potentially $3n-6$) edges the resulting graph admits a $2$-page book embedding.

(joint work with Jean Cardinal, Vincent Kusters, Csaba D. Tóth, and Manuel Wettstein)