Arc diagrams, flip distances, and Hamiltonian triangulations 🗓 🗺
Tuesday May 19th 2015 at 12:00
Department of Engineering
Section of Computer Science and Automation
Via della Vasca Navale, 79
Meeting room (1.10) on 1st floor
Dr. Michael Hoffmann, ETH Zürich
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>=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 3n/5-c 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 ~5.2n to ~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)