Document Open Access Logo

Rainbow Cycles in Flip Graphs

Authors Stefan Felsner, Linda Kleist, Torsten Mütze, Leon Sering

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.38.pdf
  • Filesize: 0.97 MB
  • 14 pages

Document Identifiers

Author Details

Stefan Felsner
Linda Kleist
Torsten Mütze
Leon Sering

Cite As Get BibTex

Stefan Felsner, Linda Kleist, Torsten Mütze, and Leon Sering. Rainbow Cycles in Flip Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.38

Abstract

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.

Subject Classification

Keywords
  • flip graph
  • cycle
  • rainbow
  • Gray code
  • triangulation
  • spanning tree
  • matching
  • permutation
  • subset
  • combination

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. O. Aichholzer, F. Aurenhammer, C. Huemer, and B. Vogtenhuber. Gray code enumeration of plane straight-line graphs. Graphs Combin., 23(5):467-479, 2007. URL: http://dx.doi.org/10.1007/s00373-007-0750-z.
  2. N. Alon, A. Pokrovskiy, and B. Sudakov. Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles. arXiv:1608.07028, Aug 2016. Google Scholar
  3. B. Alspach. The wonderful Walecki construction. Bull. Inst. Combin. Appl., 52:7-20, 2008. Google Scholar
  4. L. D. Andersen. Hamilton circuits with many colours in properly edge-coloured complete graphs. Mathematica Scandinavica, 64:5-14, 1989. Google Scholar
  5. J. Balogh and T. Molla. Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs. arXiv:1706.04950, Jun 2017. Google Scholar
  6. G. S. Bhat and C. D. Savage. Balanced Gray codes. Electron. J. Combin., 3(1):Research Paper 25, approx. 11 pp., 1996. URL: http://www.combinatorics.org/Volume_3/Abstracts/v3i1r25.html.
  7. P. Bose and F. Hurtado. Flips in planar graphs. Comput. Geom., 42(1):60-80, 2009. URL: http://dx.doi.org/10.1016/j.comgeo.2008.04.001.
  8. M. Buck and D. Wiedemann. Gray codes with restricted density. Discrete Math., 48(2-3):163-171, 1984. URL: http://dx.doi.org/10.1016/0012-365X(84)90179-1.
  9. C. Ceballos, F. Santos, and G. M. Ziegler. Many non-equivalent realizations of the associahedron. Combinatorica, 35(5):513-551, 2015. URL: http://dx.doi.org/10.1007/s00493-014-2959-9.
  10. P. Eades, M. Hickey, and R. C. Read. Some Hamilton paths and a minimal change algorithm. J. Assoc. Comput. Mach., 31(1):19-29, 1984. URL: http://dx.doi.org/10.1145/2422.322413.
  11. D. Eppstein. Happy endings for flip graphs. J. Comput. Geom., 1(1):3-28, 2010. Google Scholar
  12. R. Fabila-Monroy, D. Flores-Peñaloza, C. Huemer, F. Hurtado, J. Urrutia, and D. R. Wood. On the chromatic number of some flip graphs. Discrete Math. Theor. Comput. Sci., 11(2):47-56, 2009. Google Scholar
  13. S. Felsner, L. Kleist, T. Mütze, and L. Sering. Rainbow cycles in flip graphs. arXiv:1712. 07421, Dec 2017. Google Scholar
  14. P. Gregor, T. Mütze, and J. Nummenpalo. A short proof of the middle levels theorem. arXiv:1710.08249, Oct 2017. Google Scholar
  15. S. Hanke, T. Ottmann, and S. Schuierer. The edge-flipping distance of triangulations. Journal of Universal Computer Science, 2(8):570-579, 1996. Google Scholar
  16. C. Hernando, F. Hurtado, and M. Noy. Graphs of non-crossing perfect matchings. Graphs Combin., 18(3):517-532, 2002. URL: http://dx.doi.org/10.1007/s003730200038.
  17. C. Huemer, F. Hurtado, M. Noy, and E. Omaña-Pulido. Gray codes for non-crossing partitions and dissections of a convex polygon. Discrete Appl. Math., 157(7):1509-1520, 2009. URL: http://dx.doi.org/10.1016/j.dam.2008.06.018.
  18. F. Hurtado and M. Noy. Graph of triangulations of a convex polygon and tree of triangulations. Comput. Geom., 13(3):179-188, 1999. URL: http://dx.doi.org/10.1016/S0925-7721(99)00016-4.
  19. F. Hurtado, M. Noy, and J. Urrutia. Flipping edges in triangulations. Discrete Comput. Geom., 22(3):333-346, 1999. URL: http://dx.doi.org/10.1007/PL00009464.
  20. S. Johnson. Generation of permutations by adjacent transposition. Math. Comp., 17:282-285, 1963. Google Scholar
  21. D. E. Knuth. The art of computer programming. Vol. 4A. Combinatorial algorithms. Part 1. Addison-Wesley, Upper Saddle River, NJ, 2011. Google Scholar
  22. V. L. Kompel'makher and V. A. Liskovets. Sequantial generation of arrangements by means of a basis of transpositions. Kibernetica, 3:17-21, 1975. Google Scholar
  23. C. W. Lee. The associahedron and triangulations of the n-gon. European J. Combin., 10(6):551-560, 1989. URL: http://dx.doi.org/10.1016/S0195-6698(89)80072-1.
  24. M. Li and L. Zhang. Better approximation of diagonal-flip transformation and rotation transformation. In Computing and Combinatorics, 4th Annual International Conference, COCOON '98, Taipei, Taiwan, R.o.C., August 12-14, 1998, Proceedings, pages 85-94, 1998. URL: http://dx.doi.org/10.1007/3-540-68535-9_12.
  25. J. M. Lucas. The rotation graph of binary trees is Hamiltonian. J. Algorithms, 8(4):503-535, 1987. URL: http://dx.doi.org/10.1016/0196-6774(87)90048-4.
  26. T. Mütze. Proof of the middle levels conjecture. Proc. Lond. Math. Soc. (3), 112(4):677-713, 2016. URL: http://dx.doi.org/10.1112/plms/pdw004.
  27. A. Nijenhuis and H. S. Wilf. Combinatorial algorithms. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, second edition, 1978. For computers and calculators, Computer Science and Applied Mathematics. Google Scholar
  28. L. Pournin. The diameter of associahedra. Adv. Math., 259:13-42, 2014. URL: http://dx.doi.org/10.1016/j.aim.2014.02.035.
  29. R. O. Rogers. On finding shortest paths in the rotation graph of binary trees. In Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999), volume 137, pages 77-95, 1999. Google Scholar
  30. F. Ruskey. Adjacent interchange generation of combinations. J. Algorithms, 9(2):162-180, 1988. URL: http://dx.doi.org/10.1016/0196-6774(88)90036-3.
  31. F. Ruskey and C. Savage. Hamilton cycles that extend transposition matchings in Cayley graphs of S_n. SIAM J. Discrete Math., 6(1):152-166, 1993. URL: http://dx.doi.org/10.1137/0406012.
  32. C. Savage. A survey of combinatorial Gray codes. SIAM Rev., 39(4):605-629, 1997. URL: http://dx.doi.org/10.1137/S0036144595295272.
  33. D. D. Sleator, R. E. Tarjan, and W. P. Thurston. Rotation distance, triangulations, and hyperbolic geometry. J. Amer. Math. Soc., 1(3):647-681, 1988. URL: http://dx.doi.org/10.2307/1990951.
  34. G. C. Tootill. The use of cyclic permuted codes in relay counting circuits. Proceedings of the IEE - Part B: Radio and Electronic Engineering, 103:432-436, April 1956. Google Scholar
  35. H. F. Trotter. Algorithm 115: Perm. Commun. ACM, 5(8):434-435, 1962. URL: http://dx.doi.org/10.1145/368637.368660.
  36. H. S. Wilf. Combinatorial algorithms: an update, volume 55 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1989. URL: http://dx.doi.org/10.1137/1.9781611970166.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact