2026-07-22T21:03:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8751 2024-03-06T10:42:34Z ddc:004 open_access

Rainbow Cycles in Flip Graphs Felsner, Stefan Kleist, Linda Mütze, Torsten Sering, Leon flip graph cycle rainbow Gray code triangulation spanning tree matching permutation subset combination The flip graph of triangulations has as vertices all triangulations of a convex n-gon, and an edge between any two triangulations that differ in exactly one edge. An r-rainbow cycle in this graph is a cycle in which every inner edge of the triangulation appears exactly r times. This notion of a rainbow cycle extends in a natural way to other flip graphs. In this paper we investigate the existence of r-rainbow cycles for three different flip graphs on classes of geometric objects: the aforementioned flip graph of triangulations of a convex n-gon, the flip graph of plane spanning trees on an arbitrary set of n points, and the flip graph of non-crossing perfect matchings on a set of n points in convex position. In addition, we consider two flip graphs on classes of non-geometric objects: the flip graph of permutations of {1,2,...,n } and the flip graph of k-element subsets of {1,2,...,n }. In each of the five settings, we prove the existence and non-existence of rainbow cycles for different values of r, n and k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Felsner and Linda Kleist and Torsten Mütze and Leon Sering 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.38 urn:nbn:de:0030-drops-87514 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.38 eng https://creativecommons.org/licenses/by/3.0/legalcode