Master’s Thesis Presentation • Algorithms and Complexity • Connectivity Properties of the Flip Graph After Forbidding Triangulation EdgesExport this event to calendar

Wednesday, September 14, 2022 — 1:30 PM to 2:30 PM EDT

Please note: This master’s thesis presentation will take place online.

Reza Bigdeli, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Anna Lubiw

The flip graph for a set $P$ of points in the plane has a vertex for every triangulation of $P$, and an edge when two triangulations differ by one flip that replaces one triangulation edge by another.

The flip graph is known to have some connectivity properties:

  1. the flip graph is connected;
  2. connectivity still holds when restricted to triangulations containing some constrained edges between the points; 
  3. for $P$ in general position of size $n$, the flip graph is $\lceil \frac{n}{2} -2 \rceil$-connected, a recent result of Wagner and Welzl (SODA 2020).

We introduce the study of connectivity properties of the flip graph when some edges between points are forbidden. An edge $e$ between two points is a flip cut edge if eliminating triangulations containing $e$ results in a disconnected flip graph.  More generally, a set $X$ of edges between points of $P$ is a flip cut set if eliminating all triangulations that contain edges of $X$ results in a disconnected flip graph. The flip cut number of $P$ is the minimum size of a flip cut set.

We give a characterization of flip cut edges that leads to an $O(n \log n)$ time algorithm to test if an edge is a flip cut edge and, with that as preprocessing, an $O(n)$ time algorithm to test if two triangulations are in the same connected component of the flip graph.  For a set of $n$ points in convex position (whose flip graph is the 1-skeleton of the associahedron) we prove that the flip cut number is $n-3$.


To join this master’s thesis presentation on Zoom, please go to https://uwaterloo.zoom.us/j/95496585205.

Location 
Online master’s thesis presentation
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
25
26
27
28
29
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
  1. 2024 (100)
    1. April (23)
    2. March (27)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)