2026-08-10T15:59:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4914 2024-03-06T10:35:32Z ddc:004 open_access

Arc Diagrams, Flip Distances, and Hamiltonian Triangulations Cardinal, Jean Hoffmann, Michael Kusters, Vincent Tóth, Csaba D. Wettstein, Manuel graph embeddings edge flips flip graph separating triangles We show that every triangulation (maximal planar graph) on n\ge 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jean Cardinal and Michael Hoffmann and Vincent Kusters and Csaba D. Tóth and Manuel Wettstein 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.197 urn:nbn:de:0030-drops-49141 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.197 eng https://creativecommons.org/licenses/by/3.0/legalcode