Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, November 06, 2014, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Michael Hoffmann
We show that every triangulation (maximal planar graph) on n >= 6 vertices can be flipped into a Hamiltonian triangulation using a sequence of less than n/2 combinatorial edge flips. The previously best upper bound uses 4-connectivity as a means to establish Hamiltonicity. But in general about 3n/5 flips are necessary to reach a 4-connected triangulation. Our result improves the upper bound on the diameter of the combinatorial flip graph of triangulations on n vertices from 5.2n − 33.6 to 5n − 23. We also show that for every triangulation on n vertices there is a simultaneous flip of less than 2n/3 edges to a 4-connected triangulation. The bound on the number of edges is tight, up to an additive constant. As another application we show 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 Tóth, and Manuel Wettstein.
Automatic MiSe System Software Version 1.4803M | admin login