20:
28:
154:
in it whenever they differ by a single interior edge. In this case, the flip operation consists in exchanging the diagonals of a convex quadrilateral. These diagonals are the interior edges by which two triangulations adjacent in the flip graph differ. The resulting flip graph is both the
1452:
in the 1930s, the flip graph of the topological sphere is connected. Among the connected flip graphs, one also finds the flip graphs of any finite 2-dimensional set of points. In higher dimensional
Euclidean spaces, the situation is much more complicated. Finite sets of points of
1200:
of a given region in the plane. In this case, a flip can be performed when two adjacent dominos cover a square: it consists in rotating these dominos by 90 degrees around the center of the square, resulting in a different domino tiling of the same region.
1006:
Two triangulations are related by a flip when they differ by exactly one of the arcs they are composed of. Note that, these two triangulations necessarily have the same number of vertices. As in the
Euclidean case, the flip graph of
708:
275:
612:
575:
1130:
A number of other flip graphs can be defined using alternative definitions of a triangulation. For instance, the flip graph whose vertices are the centrally-symmetric triangulations of a
428:
1480:
1378:
1281:
1744:
1434:
1402:
1309:
1252:
1053:
1029:
1001:
974:
938:
894:
834:
810:
786:
371:
319:
1698:
738:
475:
398:
1642:
498:
1163:
1616:
1345:
197:
148:
124:
1801:
1669:
1587:
1567:
1539:
1500:
1187:
1120:
1100:
1073:
914:
854:
762:
620:
538:
518:
448:
339:
295:
232:
104:
1193:. One can also consider an alternative flip graph of a topological surface, defined by allowing multiple arcs and loops in the triangulations of this surface.
2022:
812:
and whose edges correspond to flips between them, is a natural generalization of the flip graph of a convex polygon, as the two flip graphs coincide when
1509:
is known to be connected. However, it is yet unknown whether the flip graphs of finite 3- and 4-dimensional sets of points are always connected or not.
59:
link two of these objects when they can be obtained from one another by an elementary operation called a flip. Flip graphs are special cases of
1746:. The diameter of the flip graphs of arbitrary topological surfaces with boundary has also been studied and is known exactly in several cases.
2411:
2084:
1196:
Flip graphs may also be defined using combinatorial objects other than triangulations. An example of such combinatorial objects are the
916:
of points on it, and connect them by arcs in such a way that any two arcs never cross. When this set of arcs is maximal, it decomposes
2338:
241:
2540:
2181:
764:. The conditions just stated, under which a flip is possible, make sure that this operation results in a triangulation of
580:
543:
1284:
2456:
1805:
2545:
1849:
1075:
vertices and whose edges correspond to flips between them. This definition can be straightforwardly extended to
2043:
1943:
1076:
403:
151:
1988:
40:
1445:
1312:
1885:
1456:
1354:
1257:
2495:
Parlier, Hugo; Pournin, Lionel (2018). "Once punctured disks, non-convex polygons, and pointihedra".
1703:
1415:
1383:
1290:
1233:
1034:
1010:
982:
955:
919:
875:
815:
791:
767:
352:
300:
2321:
Bose, Prosenjit; Verdonschot, Sander (2012). "A History of Flips in
Combinatorial Triangulations".
949:
865:
235:
2497:
2274:
1518:
1674:
1165:-gon and whose edges correspond to the operation of doing two centrally-symmetric flips is the
716:
453:
376:
60:
31:
Examples of flips in dimension 1 (top-right), 2 (top-left and central row), and 3 (bottom row).
1621:
483:
23:
The flip graphs of a quadrilateral (top-left), a pentagon (top-right), and a hexagon (bottom).
2135:
2130:
2079:
1923:
127:
44:
1133:
2307:
2214:
2166:
2117:
2066:
2001:
1966:
1901:
1872:
1828:
1592:
1318:
170:
1919:
703:{\displaystyle X{\mathord {\star }}{Y}=\{x\cup {y}:(x,y)\in {X{\mathord {\times }}{Y}}\},}
133:
109:
8:
56:
2506:
2465:
2420:
2375:
2283:
2190:
2144:
1786:
1654:
1572:
1552:
1524:
1485:
1172:
1105:
1085:
1058:
899:
869:
839:
747:
741:
523:
503:
433:
324:
280:
217:
89:
2253:
2236:
1863:
1819:
1517:
The maximum number of flips required to transform a triangulation into another is the
2344:
2334:
2057:
1983:
1957:
1760:
1003:
that can be obtained from one another by a continuous transformation are identical.
2516:
2475:
2430:
2385:
2326:
2293:
2248:
2232:
2200:
2154:
2103:
2093:
2052:
1952:
1858:
1814:
1546:
2098:
2303:
2210:
2179:
Pournin, Lionel (2013), "The flip-Graph of the 4-dimensional cube is connected",
2162:
2113:
2062:
1997:
1962:
1897:
1868:
1824:
1409:
1348:
1223:
945:
478:
2330:
1986:; Kapranov, Mikhail M. (1990), "Newton polytopes of principal A-determinants",
1979:
1651:
provided a quadratic upper bound on the diameter of the flip graph of a set of
941:
160:
2520:
2480:
2451:
2298:
2269:
2205:
2158:
2534:
2348:
2228:
1844:
1755:
1542:
1215:
1197:
200:
156:
71:
48:
2017:
1648:
1449:
346:
1671:
unmarked points on the sphere. The current upper bound on the diameter is
1219:
1190:
788:. The corresponding flip graph, whose vertices are the triangulations of
75:
2435:
2406:
1405:
1227:
1166:
164:
67:
2108:
1941:
Negami, Seiya (1994), "Diagonal flips in triangulations of surfaces",
1102:-gon, as the two coincide when the surface is a topological disk with
2149:
2082:(2000), "A point set whose space of triangulations is disconnected",
1506:
1930:. Algorithms and Computation in Mathematics. Vol. 25. Springer.
1380:. The subgraph induced by these triangulations in the flip graph of
2511:
2470:
2380:
52:
2425:
2390:
2363:
2288:
2195:
2325:. Berlin, Heidelberg: Springer Berlin Heidelberg. p. 29–44.
1647:
The diameter of other flip graphs has been studied. For instance
342:
206:
This basic construction can be generalized in a number of ways.
1978:
1783:
1521:
of the flip graph. The diameter of the flip graph of a convex
19:
2237:"Rotation distance, triangulations, and hyperbolic geometry"
1888:(1962), "The algebra of bracketings and their enumeration",
27:
864:
Another kind of flip graphs is obtained by considering the
209:
2041:
Lawson, Charles L. (1972), "Transforming triangulations",
1928:
Triangulations, Structures for
Algorithms and Applications
321:
by a flip. This operation consists in modifying the way
1482:
with disconnected flip graphs have been found whenever
450:, and if all the cells (faces of maximal dimension) of
1031:
is the graph whose vertices are the triangulations of
270:{\displaystyle {\mathcal {A}}\subset \mathbb {R} ^{d}}
2226:
1789:
1706:
1677:
1657:
1624:
1595:
1575:
1555:
1527:
1488:
1459:
1418:
1386:
1357:
1321:
1293:
1260:
1236:
1175:
1136:
1108:
1088:
1061:
1037:
1013:
985:
958:
922:
902:
878:
842:
818:
794:
770:
750:
719:
623:
583:
546:
526:
506:
486:
456:
436:
406:
379:
355:
327:
303:
283:
244:
220:
173:
136:
112:
92:
2023:
Jahresbericht der
Deutschen Mathematiker-Vereinigung
1918:
1569:
is sufficiently large and by Lionel
Pournin for all
944:(distinct arcs with the same pair of vertices), nor
607:{\displaystyle \lambda {\mathord {\star }}\tau ^{+}}
570:{\displaystyle \lambda {\mathord {\star }}\tau ^{-}}
16:
A graph that encodes local operations in mathematics
1795:
1738:
1692:
1663:
1636:
1610:
1581:
1561:
1533:
1494:
1474:
1428:
1396:
1372:
1339:
1303:
1275:
1246:
1181:
1157:
1114:
1094:
1082:The flip graph of a surface generalises that of a
1067:
1047:
1023:
995:
968:
932:
908:
888:
848:
828:
804:
780:
756:
732:
702:
606:
569:
532:
512:
492:
469:
442:
422:
392:
365:
333:
313:
289:
269:
226:
191:
142:
118:
98:
2364:"A Lower Bound on the Diameter of the Flip Graph"
2532:
2320:
2133:(2005), "Non-connected toric Hilbert schemes",
2494:
2449:
2407:"Flip-graph moduli spaces of filling surfaces"
2404:
86:A prototypical flip graph is that of a convex
2020:(1936), "Bemerkungen zum Vierfarbenproblem",
1444:Polytopal flip graphs are, by this property,
2412:Journal of the European Mathematical Society
2241:Journal of the American Mathematical Society
2085:Journal of the American Mathematical Society
2012:
2010:
940:into triangles. If in addition there are no
694:
642:
66:Among noticeable flip graphs, one finds the
2452:"Modular flip-graphs of one holed surfaces"
277:. Under some conditions, one may transform
1541:-gon has been obtained by Daniel Sleator,
2510:
2479:
2469:
2434:
2424:
2389:
2379:
2297:
2287:
2252:
2204:
2194:
2148:
2107:
2097:
2056:
2007:
1956:
1862:
1818:
1462:
1360:
1263:
373:). More precisely, if some triangulation
257:
1505:The flip graph of the vertex set of the
210:Finite sets of points in Euclidean space
26:
18:
2450:Parlier, Hugo; Pournin, Lionel (2018).
2405:Parlier, Hugo; Pournin, Lionel (2017).
2267:
2178:
979:In this setting, two triangulations of
859:
836:is the set of the vertices of a convex
423:{\displaystyle z\subset {\mathcal {A}}}
2533:
2129:
2078:
2040:
2016:
1940:
1884:
1843:
1700:, while the best-known lower bound is
2361:
2182:Discrete & Computational Geometry
1914:
1912:
1910:
1311:are the ones that can be obtained by
520:, then one can perform a flip within
126:. The vertices of this graph are the
1839:
1837:
1778:
1776:
1125:
744:, the unique other triangulation of
2368:Electronic Journal of Combinatorics
1782:
13:
1972:
1907:
1847:(2003), "A type-B associahedron",
1724:
1421:
1389:
1296:
1239:
1230:is a flip graph. For instance, if
1040:
1016:
988:
961:
925:
881:
821:
797:
773:
415:
358:
306:
247:
14:
2557:
2457:European Journal of Combinatorics
2323:Lecture Notes in Computer Science
2254:10.1090/s0894-0347-1988-0928904-4
1834:
1806:European Journal of Combinatorics
1773:
1475:{\displaystyle \mathbb {R} ^{d}}
1439:
1373:{\displaystyle \mathbb {R} ^{d}}
1276:{\displaystyle \mathbb {R} ^{d}}
2488:
2443:
2398:
2355:
2314:
2261:
2220:
2172:
2123:
1850:Advances in Applied Mathematics
1739:{\displaystyle 7n/3+\Theta (1)}
1209:
1122:points placed on its boundary.
2270:"The diameter of associahedra"
2072:
2034:
1934:
1878:
1733:
1727:
1429:{\displaystyle {\mathcal {A}}}
1397:{\displaystyle {\mathcal {A}}}
1334:
1322:
1304:{\displaystyle {\mathcal {A}}}
1247:{\displaystyle {\mathcal {A}}}
1152:
1137:
1048:{\displaystyle {\mathcal {S}}}
1024:{\displaystyle {\mathcal {S}}}
996:{\displaystyle {\mathcal {S}}}
969:{\displaystyle {\mathcal {S}}}
933:{\displaystyle {\mathcal {S}}}
889:{\displaystyle {\mathcal {S}}}
829:{\displaystyle {\mathcal {A}}}
805:{\displaystyle {\mathcal {A}}}
781:{\displaystyle {\mathcal {A}}}
671:
659:
366:{\displaystyle {\mathcal {A}}}
314:{\displaystyle {\mathcal {A}}}
297:into another triangulation of
186:
174:
1:
2099:10.1090/S0894-0347-00-00330-1
1864:10.1016/S0196-8858(02)00522-5
1820:10.1016/S0195-6698(89)80072-1
1766:
1254:is a finite set of points in
1226:have the property that their
1204:
1077:bordered topological surfaces
948:, this set of arcs defines a
150:, and two triangulations are
2058:10.1016/0012-365X(72)90093-3
1989:Soviet Mathematics - Doklady
1958:10.1016/0012-365X(93)E0101-9
1589:. This diameter is equal to
1412:, the secondary polytope of
7:
2541:Application-specific graphs
2331:10.1007/978-3-642-34191-5_3
1890:Nieuw Archief voor Wiskunde
1749:
1512:
81:
10:
2562:
872:: consider such a surface
238:of a finite set of points
2521:10.1007/s00026-018-0393-1
2481:10.1016/j.ejc.2017.07.003
2299:10.1016/j.aim.2014.02.035
2206:10.1007/s00454-013-9488-y
2159:10.1007/s00208-005-0643-5
1693:{\displaystyle 5.2n-33.6}
742:Radon's partition theorem
733:{\displaystyle \tau ^{+}}
470:{\displaystyle \tau ^{-}}
393:{\displaystyle \tau ^{-}}
2362:Frati, Fabrizio (2017).
2268:Pournin, Lionel (2014).
1637:{\displaystyle n\geq 13}
1507:4-dimensional hypercube
896:, place a finite number
493:{\displaystyle \lambda }
2498:Annals of Combinatorics
2275:Advances in Mathematics
2546:Geometric graph theory
1984:Zelevinskiĭ, Andrei V.
1797:
1740:
1694:
1665:
1638:
1612:
1583:
1563:
1535:
1496:
1476:
1430:
1398:
1374:
1341:
1305:
1285:regular triangulations
1277:
1248:
1183:
1159:
1158:{\displaystyle (2d+2)}
1116:
1096:
1069:
1049:
1025:
997:
970:
934:
910:
890:
850:
830:
806:
782:
758:
734:
704:
608:
571:
534:
514:
494:
471:
444:
424:
394:
367:
335:
315:
291:
271:
228:
193:
144:
120:
100:
32:
24:
2136:Mathematische Annalen
1798:
1741:
1695:
1666:
1639:
1613:
1611:{\displaystyle 2n-10}
1584:
1564:
1536:
1497:
1477:
1431:
1399:
1375:
1342:
1340:{\displaystyle (d+1)}
1306:
1278:
1249:
1184:
1160:
1117:
1097:
1070:
1050:
1026:
998:
971:
935:
911:
891:
851:
831:
807:
783:
759:
735:
705:
609:
572:
535:
515:
495:
472:
445:
425:
395:
368:
336:
316:
292:
272:
229:
194:
192:{\displaystyle (n-3)}
145:
121:
101:
70:of polytopes such as
30:
22:
2233:Thurston, William P.
2227:Sleator, Daniel D.;
2044:Discrete Mathematics
1944:Discrete Mathematics
1787:
1704:
1675:
1655:
1622:
1593:
1573:
1553:
1525:
1486:
1457:
1416:
1384:
1355:
1319:
1291:
1258:
1234:
1173:
1134:
1106:
1086:
1059:
1035:
1011:
983:
956:
920:
900:
876:
860:Topological surfaces
840:
816:
792:
768:
748:
717:
621:
581:
544:
524:
504:
484:
454:
434:
404:
377:
353:
325:
301:
281:
242:
218:
171:
143:{\displaystyle \pi }
134:
119:{\displaystyle \pi }
110:
90:
1980:Gel'fand, Izrail M.
870:topological surface
55:objects, and whose
1920:De Loera, Jesús A.
1793:
1736:
1690:
1661:
1634:
1608:
1579:
1559:
1531:
1492:
1472:
1426:
1394:
1370:
1337:
1301:
1273:
1244:
1179:
1155:
1112:
1092:
1065:
1045:
1021:
993:
966:
930:
906:
886:
846:
826:
802:
778:
754:
730:
700:
604:
567:
530:
510:
490:
467:
440:
420:
390:
363:
347:affinely dependent
331:
311:
287:
267:
224:
189:
140:
116:
96:
35:In mathematics, a
33:
25:
2340:978-3-642-34190-8
2229:Tarjan, Robert E.
2131:Santos, Francisco
2080:Santos, Francisco
1924:Santos, Francisco
1796:{\displaystyle n}
1761:Rotation distance
1664:{\displaystyle n}
1582:{\displaystyle n}
1562:{\displaystyle n}
1534:{\displaystyle n}
1495:{\displaystyle d}
1182:{\displaystyle d}
1126:Other flip graphs
1115:{\displaystyle n}
1095:{\displaystyle n}
1068:{\displaystyle n}
909:{\displaystyle n}
849:{\displaystyle n}
757:{\displaystyle z}
533:{\displaystyle T}
513:{\displaystyle T}
443:{\displaystyle T}
334:{\displaystyle T}
290:{\displaystyle T}
227:{\displaystyle T}
99:{\displaystyle n}
2553:
2525:
2524:
2514:
2492:
2486:
2485:
2483:
2473:
2447:
2441:
2440:
2438:
2436:10.4171/JEMS/726
2428:
2419:(9): 2697–2737.
2402:
2396:
2395:
2393:
2383:
2359:
2353:
2352:
2318:
2312:
2311:
2301:
2291:
2265:
2259:
2258:
2256:
2224:
2218:
2217:
2208:
2198:
2176:
2170:
2169:
2152:
2127:
2121:
2120:
2111:
2101:
2076:
2070:
2069:
2060:
2038:
2032:
2031:
2014:
2005:
2004:
1976:
1970:
1969:
1960:
1951:(1–3): 225–232,
1938:
1932:
1931:
1922:; Rambau, Jörg;
1916:
1905:
1904:
1882:
1876:
1875:
1866:
1841:
1832:
1831:
1822:
1802:
1800:
1799:
1794:
1780:
1745:
1743:
1742:
1737:
1717:
1699:
1697:
1696:
1691:
1670:
1668:
1667:
1662:
1643:
1641:
1640:
1635:
1617:
1615:
1614:
1609:
1588:
1586:
1585:
1580:
1568:
1566:
1565:
1560:
1547:William Thurston
1540:
1538:
1537:
1532:
1501:
1499:
1498:
1493:
1481:
1479:
1478:
1473:
1471:
1470:
1465:
1435:
1433:
1432:
1427:
1425:
1424:
1403:
1401:
1400:
1395:
1393:
1392:
1379:
1377:
1376:
1371:
1369:
1368:
1363:
1346:
1344:
1343:
1338:
1315:some faces of a
1310:
1308:
1307:
1302:
1300:
1299:
1282:
1280:
1279:
1274:
1272:
1271:
1266:
1253:
1251:
1250:
1245:
1243:
1242:
1188:
1186:
1185:
1180:
1164:
1162:
1161:
1156:
1121:
1119:
1118:
1113:
1101:
1099:
1098:
1093:
1074:
1072:
1071:
1066:
1054:
1052:
1051:
1046:
1044:
1043:
1030:
1028:
1027:
1022:
1020:
1019:
1002:
1000:
999:
994:
992:
991:
975:
973:
972:
967:
965:
964:
939:
937:
936:
931:
929:
928:
915:
913:
912:
907:
895:
893:
892:
887:
885:
884:
855:
853:
852:
847:
835:
833:
832:
827:
825:
824:
811:
809:
808:
803:
801:
800:
787:
785:
784:
779:
777:
776:
763:
761:
760:
755:
739:
737:
736:
731:
729:
728:
709:
707:
706:
701:
693:
692:
687:
686:
655:
638:
633:
632:
613:
611:
610:
605:
603:
602:
593:
592:
576:
574:
573:
568:
566:
565:
556:
555:
539:
537:
536:
531:
519:
517:
516:
511:
499:
497:
496:
491:
476:
474:
473:
468:
466:
465:
449:
447:
446:
441:
429:
427:
426:
421:
419:
418:
399:
397:
396:
391:
389:
388:
372:
370:
369:
364:
362:
361:
340:
338:
337:
332:
320:
318:
317:
312:
310:
309:
296:
294:
293:
288:
276:
274:
273:
268:
266:
265:
260:
251:
250:
233:
231:
230:
225:
198:
196:
195:
190:
149:
147:
146:
141:
125:
123:
122:
117:
105:
103:
102:
97:
61:geometric graphs
2561:
2560:
2556:
2555:
2554:
2552:
2551:
2550:
2531:
2530:
2529:
2528:
2493:
2489:
2448:
2444:
2403:
2399:
2360:
2356:
2341:
2319:
2315:
2266:
2262:
2225:
2221:
2177:
2173:
2128:
2124:
2077:
2073:
2039:
2035:
2015:
2008:
1977:
1973:
1939:
1935:
1917:
1908:
1883:
1879:
1842:
1835:
1788:
1785:
1784:
1781:
1774:
1769:
1752:
1713:
1705:
1702:
1701:
1676:
1673:
1672:
1656:
1653:
1652:
1623:
1620:
1619:
1594:
1591:
1590:
1574:
1571:
1570:
1554:
1551:
1550:
1526:
1523:
1522:
1515:
1502:is at least 5.
1487:
1484:
1483:
1466:
1461:
1460:
1458:
1455:
1454:
1442:
1420:
1419:
1417:
1414:
1413:
1388:
1387:
1385:
1382:
1381:
1364:
1359:
1358:
1356:
1353:
1352:
1320:
1317:
1316:
1295:
1294:
1292:
1289:
1288:
1267:
1262:
1261:
1259:
1256:
1255:
1238:
1237:
1235:
1232:
1231:
1212:
1207:
1174:
1171:
1170:
1135:
1132:
1131:
1128:
1107:
1104:
1103:
1087:
1084:
1083:
1060:
1057:
1056:
1039:
1038:
1036:
1033:
1032:
1015:
1014:
1012:
1009:
1008:
987:
986:
984:
981:
980:
960:
959:
957:
954:
953:
924:
923:
921:
918:
917:
901:
898:
897:
880:
879:
877:
874:
873:
862:
841:
838:
837:
820:
819:
817:
814:
813:
796:
795:
793:
790:
789:
772:
771:
769:
766:
765:
749:
746:
745:
724:
720:
718:
715:
714:
688:
682:
681:
677:
651:
634:
628:
627:
622:
619:
618:
598:
594:
588:
587:
582:
579:
578:
561:
557:
551:
550:
545:
542:
541:
525:
522:
521:
505:
502:
501:
485:
482:
481:
461:
457:
455:
452:
451:
435:
432:
431:
430:is a subset of
414:
413:
405:
402:
401:
384:
380:
378:
375:
374:
357:
356:
354:
351:
350:
341:triangulates a
326:
323:
322:
305:
304:
302:
299:
298:
282:
279:
278:
261:
256:
255:
246:
245:
243:
240:
239:
219:
216:
215:
212:
172:
169:
168:
135:
132:
131:
111:
108:
107:
91:
88:
87:
84:
17:
12:
11:
5:
2559:
2549:
2548:
2543:
2527:
2526:
2505:(3): 619–640.
2487:
2442:
2397:
2354:
2339:
2313:
2260:
2247:(3): 647–681.
2219:
2171:
2122:
2071:
2033:
2006:
1971:
1933:
1906:
1877:
1845:Simion, Rodica
1833:
1813:(6): 551–560,
1792:
1771:
1770:
1768:
1765:
1764:
1763:
1758:
1751:
1748:
1735:
1732:
1729:
1726:
1723:
1720:
1716:
1712:
1709:
1689:
1686:
1683:
1680:
1660:
1633:
1630:
1627:
1607:
1604:
1601:
1598:
1578:
1558:
1530:
1514:
1511:
1491:
1469:
1464:
1448:. As shown by
1441:
1438:
1423:
1391:
1367:
1362:
1336:
1333:
1330:
1327:
1324:
1298:
1270:
1265:
1241:
1222:, a number of
1211:
1208:
1206:
1203:
1198:domino tilings
1178:
1154:
1151:
1148:
1145:
1142:
1139:
1127:
1124:
1111:
1091:
1064:
1042:
1018:
990:
963:
927:
905:
883:
866:triangulations
861:
858:
845:
823:
799:
775:
753:
727:
723:
711:
710:
699:
696:
691:
685:
680:
676:
673:
670:
667:
664:
661:
658:
654:
650:
647:
644:
641:
637:
631:
626:
601:
597:
591:
586:
564:
560:
554:
549:
529:
509:
489:
477:have the same
464:
460:
439:
417:
412:
409:
387:
383:
360:
330:
308:
286:
264:
259:
254:
249:
223:
211:
208:
188:
185:
182:
179:
176:
161:Tamari lattice
139:
128:triangulations
115:
95:
83:
80:
15:
9:
6:
4:
3:
2:
2558:
2547:
2544:
2542:
2539:
2538:
2536:
2522:
2518:
2513:
2508:
2504:
2500:
2499:
2491:
2482:
2477:
2472:
2467:
2463:
2459:
2458:
2453:
2446:
2437:
2432:
2427:
2422:
2418:
2414:
2413:
2408:
2401:
2392:
2391:10.37236/5489
2387:
2382:
2377:
2373:
2369:
2365:
2358:
2350:
2346:
2342:
2336:
2332:
2328:
2324:
2317:
2309:
2305:
2300:
2295:
2290:
2285:
2281:
2277:
2276:
2271:
2264:
2255:
2250:
2246:
2242:
2238:
2234:
2230:
2223:
2216:
2212:
2207:
2202:
2197:
2192:
2188:
2184:
2183:
2175:
2168:
2164:
2160:
2156:
2151:
2146:
2142:
2138:
2137:
2132:
2126:
2119:
2115:
2110:
2105:
2100:
2095:
2091:
2087:
2086:
2081:
2075:
2068:
2064:
2059:
2054:
2050:
2046:
2045:
2037:
2029:
2025:
2024:
2019:
2018:Wagner, Klaus
2013:
2011:
2003:
1999:
1995:
1991:
1990:
1985:
1981:
1975:
1968:
1964:
1959:
1954:
1950:
1946:
1945:
1937:
1929:
1925:
1921:
1915:
1913:
1911:
1903:
1899:
1895:
1891:
1887:
1881:
1874:
1870:
1865:
1860:
1857:(1–2): 2–25,
1856:
1852:
1851:
1846:
1840:
1838:
1830:
1826:
1821:
1816:
1812:
1808:
1807:
1790:
1779:
1777:
1772:
1762:
1759:
1757:
1756:Flip distance
1754:
1753:
1747:
1730:
1721:
1718:
1714:
1710:
1707:
1687:
1684:
1681:
1678:
1658:
1650:
1645:
1631:
1628:
1625:
1605:
1602:
1599:
1596:
1576:
1556:
1548:
1544:
1543:Robert Tarjan
1528:
1520:
1510:
1508:
1503:
1489:
1467:
1451:
1447:
1440:Connectedness
1437:
1411:
1407:
1365:
1350:
1347:-dimensional
1331:
1328:
1325:
1314:
1286:
1268:
1229:
1225:
1221:
1217:
1202:
1199:
1194:
1192:
1189:-dimensional
1176:
1168:
1149:
1146:
1143:
1140:
1123:
1109:
1089:
1080:
1078:
1062:
1004:
977:
951:
950:triangulation
947:
943:
942:multiple arcs
903:
871:
867:
857:
843:
751:
743:
725:
721:
697:
689:
683:
678:
674:
668:
665:
662:
656:
652:
648:
645:
639:
635:
629:
624:
617:
616:
615:
599:
595:
589:
584:
562:
558:
552:
547:
540:by replacing
527:
507:
487:
480:
462:
458:
437:
410:
407:
400:of a circuit
385:
381:
348:
345:(a minimally
344:
328:
284:
262:
252:
237:
236:triangulation
221:
207:
204:
202:
201:associahedron
199:-dimensional
183:
180:
177:
166:
162:
158:
157:Hasse diagram
153:
137:
129:
113:
93:
79:
77:
73:
69:
64:
62:
58:
54:
50:
49:combinatorial
46:
42:
38:
29:
21:
2502:
2496:
2490:
2461:
2455:
2445:
2416:
2410:
2400:
2374:(1): P1.43.
2371:
2367:
2357:
2322:
2316:
2279:
2273:
2263:
2244:
2240:
2222:
2186:
2180:
2174:
2150:math/0204044
2140:
2134:
2125:
2089:
2083:
2074:
2048:
2042:
2036:
2027:
2021:
1993:
1987:
1974:
1948:
1942:
1936:
1927:
1893:
1892:, Series 3,
1889:
1880:
1854:
1848:
1810:
1804:
1649:Klaus Wagner
1646:
1516:
1504:
1450:Klaus Wagner
1443:
1216:associahedra
1213:
1210:Polytopality
1195:
1129:
1081:
1005:
978:
863:
712:
213:
205:
85:
72:associahedra
65:
36:
34:
2464:: 158–173.
2189:: 511–530,
2143:: 645–665,
2092:: 611–637,
2051:: 365–372,
1996:: 278–281,
1896:: 131–146,
1886:Tamari, Dov
1214:Apart from
1191:cyclohedron
2535:Categories
2512:1602.04576
2471:1510.07664
2381:1508.03473
2109:10902/2584
1767:References
1406:1-skeleton
1313:projecting
1228:1-skeleton
1220:cyclohedra
1205:Properties
1167:1-skeleton
349:subset of
165:1-skeleton
76:cyclohedra
68:1-skeleton
37:flip graph
2426:1407.1516
2349:0302-9743
2289:1207.6296
2282:: 13–42.
2196:1201.6543
1725:Θ
1685:−
1629:≥
1603:−
1446:connected
1224:polytopes
722:τ
684:×
675:∈
649:∪
630:⋆
596:τ
590:⋆
585:λ
563:−
559:τ
553:⋆
548:λ
488:λ
463:−
459:τ
411:⊂
386:−
382:τ
253:⊂
181:−
138:π
114:π
53:geometric
2235:(1988).
1926:(2010).
1750:See also
1519:diameter
1513:Diameter
1410:polytope
1349:polytope
614:, where
163:and the
152:adjacent
82:Examples
45:vertices
2308:3197650
2215:3038527
2167:2181765
2118:1758756
2067:0311491
2030:: 26–32
2002:1020882
1967:1310882
1902:0146227
1873:1979780
1829:1022776
1803:-gon",
1404:is the
1169:of the
740:is, by
343:circuit
167:of the
159:of the
2347:
2337:
2306:
2213:
2165:
2116:
2065:
2000:
1965:
1900:
1871:
1827:
1545:, and
1283:, the
856:-gon.
43:whose
2507:arXiv
2466:arXiv
2421:arXiv
2376:arXiv
2284:arXiv
2191:arXiv
2145:arXiv
1618:when
1549:when
1408:of a
1055:with
946:loops
868:of a
234:be a
106:-gon
57:edges
41:graph
39:is a
2345:ISSN
2335:ISBN
1688:33.6
1218:and
713:and
479:link
214:Let
47:are
2517:doi
2476:doi
2431:doi
2386:doi
2327:doi
2294:doi
2280:259
2249:doi
2201:doi
2155:doi
2141:332
2104:hdl
2094:doi
2053:doi
1953:doi
1949:135
1859:doi
1815:doi
1679:5.2
1351:on
1287:of
952:of
577:by
500:in
130:of
74:or
51:or
2537::
2515:.
2503:22
2501:.
2474:.
2462:67
2460:.
2454:.
2429:.
2417:19
2415:.
2409:.
2384:.
2372:24
2370:.
2366:.
2343:.
2333:.
2304:MR
2302:.
2292:.
2278:.
2272:.
2243:.
2239:.
2231:;
2211:MR
2209:,
2199:,
2187:49
2185:,
2163:MR
2161:,
2153:,
2139:,
2114:MR
2112:,
2102:,
2090:13
2088:,
2063:MR
2061:,
2047:,
2028:46
2026:,
2009:^
1998:MR
1994:40
1992:,
1982:;
1963:MR
1961:,
1947:,
1909:^
1898:MR
1894:10
1869:MR
1867:,
1855:30
1853:,
1836:^
1825:MR
1823:,
1811:10
1809:,
1775:^
1644:.
1632:13
1606:10
1436:.
1079:.
976:.
203:.
78:.
63:.
2523:.
2519::
2509::
2484:.
2478::
2468::
2439:.
2433::
2423::
2394:.
2388::
2378::
2351:.
2329::
2310:.
2296::
2286::
2257:.
2251::
2245:1
2203::
2193::
2157::
2147::
2106::
2096::
2055::
2049:3
1955::
1861::
1817::
1791:n
1734:)
1731:1
1728:(
1722:+
1719:3
1715:/
1711:n
1708:7
1682:n
1659:n
1626:n
1600:n
1597:2
1577:n
1557:n
1529:n
1490:d
1468:d
1463:R
1422:A
1390:A
1366:d
1361:R
1335:)
1332:1
1329:+
1326:d
1323:(
1297:A
1269:d
1264:R
1240:A
1177:d
1153:)
1150:2
1147:+
1144:d
1141:2
1138:(
1110:n
1090:n
1063:n
1041:S
1017:S
989:S
962:S
926:S
904:n
882:S
844:n
822:A
798:A
774:A
752:z
726:+
698:,
695:}
690:Y
679:X
672:)
669:y
666:,
663:x
660:(
657::
653:y
646:x
643:{
640:=
636:Y
625:X
600:+
528:T
508:T
438:T
416:A
408:z
359:A
329:T
307:A
285:T
263:d
258:R
248:A
222:T
187:)
184:3
178:n
175:(
94:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.