2016/11/08 by Jean Cardinal, Michael Hoffmann, Cardinal, Jean +7 · 3 citations
Computer Science · #05C45 #05C62 #68R10 #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences #G.2.2 #acm:05C45 #acm:05C62 #acm:68R10 #cs.CG #msc:05C45 #msc:05C62 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1611.02541
29 pages, full version of our STACS 2015 paper corrected wrong author affiliation marks from v1
arxiv created 2016/11/11 · arxiv updated 2016/11/14
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 flip graph of combinatorial 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.