Flips and Flip-Graphs -- Sommersemester 2022

Ausgewählte Kapitel der Graphentheorie:
Flips and Flip-Graphs

Sommersemester 2022
Prof. Stefan Felsner
Sprechstunde n.V.

LV-Nr.: 3236 L 316


Hinweise für Seminarvorträge:


References -- Quellen:

  1. Connectivity of Triangulation Flip Graphs in the Plane
    Uli Wagner and Emo Welzl
    Symposium on Discrete Algorithms (SODA) 2020
    1. Diagonal Flips in Hamiltonian Triangulations on the Sphere
      Ryuichi Mori, Atsuhiro Nakamoto, and Katsuhiro Ota
      Graphs and Combinatorics 19 (2003) 413–418
    2. Making triangulations 4-connected using flips
      Prosenjit Bose, Dana Jansens, André van Renssen, Maria Saumell, and Sander Verdonschot
      Computational Geometry 47 (2014) 187–197
  2. Sweeps, arrangements and signotopes
    Stefan Felsner and Helmut Weil
    Discrete Applied Mathematics 109 (2001) 67–94
  3. Happy Endings for Flip Graphs
    David Eppstein
    Journal of Computational Geometry 1(1)(2010) 3-28
  4. T-tetrominoes tiling’s Markov chain mixes fast
    K.K. Kayibi and S. Pirzada
    Theoretical Computer Science 714 (2018) 1–14
  5. Mixing Times of Markov Chains on Degree Constrained Orientations of Planar Graphs
    Stefan Felsner and Daniel Heldt
    Discrete Mathematics and Theoretical Computer Science 18 (2016) #20
  6. Using contracted solution graphs for solving reconfiguration problems
    Paul Bonsma and Daniël Paulusma
    Acta Informatica 56 (2019) 619–648
  7. Enumerating degree sequences in digraphs and a cycle–cocycle reversing system
    Emeric Gioan
    European Journal of Combinatorics 28 (2007) 1351–1366
  8. Graph Properties of Graph Associahedra
    Thibault Manneville and Vincent Pilaud
    Séminaire Lotharingien de Combinatoire 73 (2015), Article B73d
  9. Flip Distances Between Graph Orientations
    Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner, and Birgit Vogtenhuber
    Algorithmica 83 (2021) 116–143
  10. Multitriangulations as Complexes of Star Polygons
    Vincent Pilaud and Francisco Santos
    Discrete and Computational Geometry 41 (2009) 284–317
  11. Lattice Structures from Planar Graphs
    Stefan Felsner
    Electronic Journal of Combinatorics 11 (2004) R15
  12. Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips)
    Uli Wagner and Emo Welzl
    Symposium on Computational Geometry (SoCG) 2020
  13. Efficient generation of elimination trees and graph associahedra
    Jean Cardinal, Arturo Merino, and Torsten Mütze
    Symposium on Discrete Algorithms (SODA) 2022
  14. Combinatorial generation via permutation languages
    Elizabeth Hartung, Hung P. Hoang, Torsten Mütze, and Aaron Williams
    Symposium on Discrete Algorithms (SODA) 2020
  15. Mixing of Permutations by Biased Transpositions
    Shahrzad Haddadan and Peter Winkler
    Theory of Computing Systems 63 (2019) 1068–1088
  16. Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and k-ARY trees
    Igor Pak
    Discrete Mathematics 204 (1999) 329-335

Zuletzt bearbeitet April 2022