Flip graph

Last updated January 16, 2024

In mathematics, a flip graph is a graph whose vertices are combinatorial or geometric objects, and whose edges 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 geometric graphs.

Examples

A prototypical flip graph is that of a convex $n$ -gon $\pi$ . The vertices of this graph are the triangulations of $\pi$ , and two triangulations are adjacent 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 Hasse diagram of the Tamari lattice ^[3] and the 1-skeleton of the $(n-3)$ -dimensional associahedron.^[1]

This basic construction can be generalized in a number of ways.

Finite sets of points in Euclidean space

Let $T$ be a triangulation of a finite set of points ${\mathcal {A}}\subset \mathbb {R} ^{d}$ . Under some conditions, one may transform $T$ into another triangulation of ${\mathcal {A}}$ by a flip. This operation consists in modifying the way $T$ triangulates a circuit (a minimally affinely dependent subset of ${\mathcal {A}}$ ). More precisely, if some triangulation $\tau ^{-}$ of a circuit $z\subset {\mathcal {A}}$ is a subset of $T$ , and if all the cells (faces of maximal dimension) of $\tau ^{-}$ have the same link $\lambda$ in $T$ , then one can perform a flip within $T$ by replacing $\lambda {\mathord {\star }}\tau ^{-}$ by $\lambda {\mathord {\star }}\tau ^{+}$ , where

X{\mathord {\star }}{Y}=\{x\cup {y}:(x,y)\in {X{\mathord {\times }}{Y}}\},

and $\tau ^{+}$ is, by Radon's partition theorem, the unique other triangulation of $z$ . The conditions just stated, under which a flip is possible, make sure that this operation results in a triangulation of ${\mathcal {A}}$ .^[4] The corresponding flip graph, whose vertices are the triangulations of ${\mathcal {A}}$ 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 ${\mathcal {A}}$ is the set of the vertices of a convex $n$ -gon.

Topological surfaces

Another kind of flip graphs is obtained by considering the triangulations of a topological surface:^[5] consider such a surface ${\mathcal {S}}$ , place a finite number $n$ 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 ${\mathcal {S}}$ into triangles. If in addition there are no multiple arcs (distinct arcs with the same pair of vertices), nor loops, this set of arcs defines a triangulation of ${\mathcal {S}}$ .

In this setting, two triangulations of ${\mathcal {S}}$ that can be obtained from one another by a continuous transformation are identical.

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 ${\mathcal {S}}$ is the graph whose vertices are the triangulations of ${\mathcal {S}}$ with $n$ vertices and whose edges correspond to flips between them. This definition can be straightforwardly extended to bordered topological surfaces.

The flip graph of a surface generalises that of a $n$ -gon, as the two coincide when the surface is a topological disk with $n$ points placed on its boundary.

Other flip graphs

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 $(2d+2)$ -gon and whose edges correspond to the operation of doing two centrally-symmetric flips is the 1-skeleton of the $d$ -dimensional cyclohedron.^[2] 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.

Flip graphs may also be defined using combinatorial objects other than triangulations. An example of such combinatorial objects are the domino tilings 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.

Properties

Polytopality

Apart from associahedra and cyclohedra, a number of polytopes have the property that their 1-skeleton is a flip graph. For instance, if ${\mathcal {A}}$ is a finite set of points in $\mathbb {R} ^{d}$ , the regular triangulations of ${\mathcal {A}}$ are the ones that can be obtained by projecting some faces of a $(d+1)$ -dimensional polytope on $\mathbb {R} ^{d}$ . The subgraph induced by these triangulations in the flip graph of ${\mathcal {A}}$ is the 1-skeleton of a polytope, the secondary polytope of ${\mathcal {A}}$ .^[6]

Connectedness

Polytopal flip graphs are, by this property, connected. As shown by Klaus Wagner in the 1930s, the flip graph of the topological sphere is connected.^[7] Among the connected flip graphs, one also finds the flip graphs of any finite 2-dimensional set of points.^[8] In higher dimensional Euclidean spaces, the situation is much more complicated. Finite sets of points of $\mathbb {R} ^{d}$ with disconnected flip graphs have been found whenever $d$ is at least 5.^[4]^[9]^[10]

The flip graph of the vertex set of the 4-dimensional hypercube is known to be connected.^[11] However, it is yet unknown whether the flip graphs of finite 3- and 4-dimensional sets of points are always connected or not.^[4]

Diameter

The maximum number of flips required to transform a triangulation into another is the diameter of the flip graph. The diameter of the flip graph of a convex $n$ -gon has been obtained by Daniel Sleator, Robert Tarjan, and William Thurston ^[12] when $n$ is sufficiently large and by Lionel Pournin for all $n$ . This diameter is equal to $2n-10$ when $n\geq 13$ .^[13]

The diameter of other flip graphs has been studied. For instance Klaus Wagner provided a quadratic upper bound on the diameter of the flip graph of a set of $n$ unmarked points on the sphere.^[7] The current upper bound on the diameter is $5.2n-33.6$ ,^[14] while the best-known lower bound is $7n/3+\Theta (1)$ .^[15] The diameter of the flip graphs of arbitrary topological surfaces with boundary has also been studied and is known exactly in several cases.^[16]^[17]^[18]

Related Research Articles

In geometry, every polyhedron is associated with a second dual structure, where the vertices of one correspond to the faces of the other, and the edges between pairs of vertices of one correspond to the edges between pairs of faces of the other. Such dual figures remain combinatorial or abstract polyhedra, but not all can also be constructed as geometric polyhedra. Starting with any given polyhedron, the dual of its dual is the original polyhedron.

In mathematics and computational geometry, a Delaunay triangulation (DT), also known as a Delone triangulation, for a given set ${p i$ } of discrete points $p i$ in general position is a triangulation such that no point $p i$ is inside the circumcircle of any triangle in the DT. Delaunay triangulations maximize the minimum of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934.

<span class="mw-page-title-main">Polyhedron</span> 3D shape with flat faces, straight edges and sharp corners

In geometry, a polyhedron is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices.

In elementary geometry, a polytope is a geometric object with flat sides (faces). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions $n$ as an $n$ -dimensional polytope or $n$ -polytope. For example, a two-dimensional polygon is a 2-polytope and a three-dimensional polyhedron is a 3-polytope. In this context, "flat sides" means that the sides of a $(k + 1)$ -polytope consist of $k$ -polytopes that may have $(k - 1)$ -polytopes in common.

In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic is a topological invariant, a number that describes a topological space's shape or structure regardless of the way it is bent. It is commonly denoted by $.$

In mathematics, an integral polytope has an associated Ehrhart polynomial that encodes the relationship between the volume of a polytope and the number of integer points the polytope contains. The theory of Ehrhart polynomials can be seen as a higher-dimensional generalization of Pick's theorem in the Euclidean plane.

In mathematics, the barycentric subdivision is a standard way to subdivide a given simplex into smaller ones. Its extension on simplicial complexes is a canonical method to refine them. Therefore, the barycentric subdivision is an important tool in algebraic topology.

The triaugmented triangular prism, in geometry, is a convex polyhedron with 14 equilateral triangles as its faces. It can be constructed from a triangular prism by attaching equilateral square pyramids to each of its three square faces. The same shape is also called the tetrakis triangular prism, tricapped trigonal prism, tetracaidecadeltahedron, or tetrakaidecadeltahedron; these last names mean a polyhedron with 14 triangular faces. It is an example of a deltahedron and of a Johnson solid.

In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a piecewise-linear Jordan curve consisting of finitely many line segments. These polygons include as special cases the convex polygons, star-shaped polygons, and monotone polygons.

In geometry, a triangulation is a subdivision of a planar object into triangles, and by extension the subdivision of a higher-dimension geometric object into simplices. Triangulations of a three-dimensional volume would involve subdividing it into tetrahedra packed together.

<span class="mw-page-title-main">Triangulation (topology)</span>

In mathematics, triangulation describes the replacement of topological spaces by piecewise linear spaces, i.e. the choice of a homeomorphism in a suitable simplicial complex. Spaces being homeomorphic to a simplicial complex are called triangulable. Triangulation has various uses in different branches of mathematics, for instance in algebraic topology, in complex analysis or in modeling.

<span class="mw-page-title-main">Convex polytope</span> Convex hull of a finite set of points in a Euclidean space

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the $-dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.$

Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geometric graphs, meaning graphs drawn in the Euclidean plane with possibly intersecting straight-line edges, and topological graphs, where the edges are allowed to be arbitrary continuous curves connecting the vertices; thus, it can be described as "the theory of geometric and topological graphs". Geometric graphs are also known as spatial networks.

In mathematical programming and polyhedral combinatorics, the Hirsch conjecture is the statement that the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n − d. That is, any two vertices of the polytope must be connected to each other by a path of length at most n − d. The conjecture was first put forth in a letter by Warren M. Hirsch to George B. Dantzig in 1957 and was motivated by the analysis of the simplex method in linear programming, as the diameter of a polytope provides a lower bound on the number of steps needed by the simplex method. The conjecture is now known to be false in general.

Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.

In mathematics, an associahedron $K n$ is an $(n - 2)$ -dimensional convex polytope in which each vertex corresponds to a way of correctly inserting opening and closing parentheses in a string of $n$ letters, and the edges correspond to single application of the associativity rule. Equivalently, the vertices of an associahedron correspond to the triangulations of a regular polygon with $n + 1$ sides and the edges correspond to edge flips in which a single diagonal is removed from a triangulation and replaced by a different diagonal. Associahedra are also called Stasheff polytopes after the work of Jim Stasheff, who rediscovered them in the early 1960s after earlier work on them by Dov Tamari.

In geometry, the cyclohedron is a $-dimensional polytope where can be any non-negative integer. It was first introduced as a combinatorial object by Raoul Bott and Clifford Taubes and, for this reason, it is also sometimes called the Bott-Taubes polytope . It was later constructed as a polytope by Martin Markl and by Rodica Simion. Rodica Simion describes this polytope as an associahedron of type B.$

In graph drawing and geometric graph theory, a Tutte embedding or barycentric embedding of a simple, 3-vertex-connected, planar graph is a crossing-free straight-line embedding with the properties that the outer face is a convex polygon and that each interior vertex is at the average of its neighbors' positions. If the outer polygon is fixed, this condition on the interior vertices determines their position uniquely as the solution to a system of linear equations. Solving the equations geometrically produces a planar embedding. Tutte's spring theorem, proven by W. T. Tutte (1963), states that this unique solution is always crossing-free, and more strongly that every face of the resulting planar embedding is convex. It is called the spring theorem because such an embedding can be found as the equilibrium position for a system of springs representing the edges of the graph.

Reverse-search algorithms are a class of algorithms for generating all objects of a given size, from certain classes of combinatorial objects. In many cases, these methods allow the objects to be generated in polynomial time per object, using only enough memory to store a constant number of objects. They work by organizing the objects to be generated into a spanning tree of their state space, and then performing a depth-first search of this tree.

In discrete mathematics and theoretical computer science, the flip distance between two triangulations of the same point set is the number of flips required to transform one triangulation into another. A flip removes an edge between two triangles in the triangulation and then adds the other diagonal in the edge's enclosing quadrilateral, forming a different triangulation of the same point set.

References

1 2 Lee, Carl (1989), "The Associahedron and Triangulations of the $n$ -gon", European Journal of Combinatorics , 10 (6): 551–560, doi: 10.1016/S0195-6698(89)80072-1 , MR 1022776
1 2 Simion, Rodica (2003), "A type-B associahedron", Advances in Applied Mathematics , 30 (1–2): 2–25, doi: 10.1016/S0196-8858(02)00522-5 , MR 1979780
↑ Tamari, Dov (1962), "The algebra of bracketings and their enumeration", Nieuw Archief voor Wiskunde, Series 3, 10: 131–146, MR 0146227
1 2 3 De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010). Triangulations, Structures for Algorithms and Applications. Algorithms and Computation in Mathematics. Vol. 25. Springer.
↑ Negami, Seiya (1994), "Diagonal flips in triangulations of surfaces", Discrete Mathematics , 135 (1–3): 225–232, doi: 10.1016/0012-365X(93)E0101-9 , MR 1310882
↑ Gel'fand, Izrail M.; Zelevinskiĭ, Andrei V.; Kapranov, Mikhail M. (1990), "Newton polytopes of principal A-determinants", Soviet Mathematics - Doklady , 40: 278–281, MR 1020882
1 2 Wagner, Klaus (1936), "Bemerkungen zum Vierfarbenproblem", Jahresbericht der Deutschen Mathematiker-Vereinigung , 46: 26–32
↑ Lawson, Charles L. (1972), "Transforming triangulations", Discrete Mathematics , 3: 365–372, doi: 10.1016/0012-365X(72)90093-3 , MR 0311491
↑ Santos, Francisco (2000), "A point set whose space of triangulations is disconnected", Journal of the American Mathematical Society , 13: 611–637, doi: 10.1090/S0894-0347-00-00330-1 , hdl: 10902/2584 , MR 1758756
↑ Santos, Francisco (2005), "Non-connected toric Hilbert schemes", Mathematische Annalen , 332: 645–665, arXiv: math/0204044 , doi:10.1007/s00208-005-0643-5, MR 2181765
↑ Pournin, Lionel (2013), "The flip-Graph of the 4-dimensional cube is connected", Discrete & Computational Geometry , 49: 511–530, arXiv: 1201.6543 , doi: 10.1007/s00454-013-9488-y , MR 3038527
↑ Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988). "Rotation distance, triangulations, and hyperbolic geometry". Journal of the American Mathematical Society. 1 (3): 647–681. doi: 10.1090/s0894-0347-1988-0928904-4 .
↑ Pournin, Lionel (2014). "The diameter of associahedra". Advances in Mathematics . 259: 13–42. arXiv: 1207.6296 . doi: 10.1016/j.aim.2014.02.035 . MR 3197650.
↑ Bose, Prosenjit; Verdonschot, Sander (2012). "A History of Flips in Combinatorial Triangulations". Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg. p. 29–44. doi:10.1007/978-3-642-34191-5_3. ISBN 978-3-642-34190-8. ISSN 0302-9743.
↑ Frati, Fabrizio (2017). "A Lower Bound on the Diameter of the Flip Graph". Electronic Journal of Combinatorics. 24 (1): P1.43. arXiv: 1508.03473 . doi: 10.37236/5489 .
↑ Parlier, Hugo; Pournin, Lionel (2017). "Flip-graph moduli spaces of filling surfaces". Journal of the European Mathematical Society . 19 (9): 2697–2737. arXiv: 1407.1516 . doi: 10.4171/JEMS/726 .
↑ Parlier, Hugo; Pournin, Lionel (2018). "Modular flip-graphs of one holed surfaces". European Journal of Combinatorics . 67: 158–173. arXiv: 1510.07664 . doi: 10.1016/j.ejc.2017.07.003 .
↑ Parlier, Hugo; Pournin, Lionel (2018). "Once punctured disks, non-convex polygons, and pointihedra". Annals of Combinatorics . 22 (3): 619–640. arXiv: 1602.04576 . doi:10.1007/s00026-018-0393-1.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[CL-1] 1 2 Lee, Carl (1989), "The Associahedron and Triangulations of the $n$ -gon", European Journal of Combinatorics , 10 (6): 551–560, doi: 10.1016/S0195-6698(89)80072-1 , MR 1022776

[RS-2] 1 2 Simion, Rodica (2003), "A type-B associahedron", Advances in Applied Mathematics , 30 (1–2): 2–25, doi: 10.1016/S0196-8858(02)00522-5 , MR 1979780

[3] Tamari, Dov (1962), "The algebra of bracketings and their enumeration", Nieuw Archief voor Wiskunde, Series 3, 10: 131–146, MR 0146227

[DRS-4] 1 2 3 De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010). Triangulations, Structures for Algorithms and Applications. Algorithms and Computation in Mathematics. Vol. 25. Springer.

[5] Negami, Seiya (1994), "Diagonal flips in triangulations of surfaces", Discrete Mathematics , 135 (1–3): 225–232, doi: 10.1016/0012-365X(93)E0101-9 , MR 1310882

[GZK-6] Gel'fand, Izrail M.; Zelevinskiĭ, Andrei V.; Kapranov, Mikhail M. (1990), "Newton polytopes of principal A-determinants", Soviet Mathematics - Doklady , 40: 278–281, MR 1020882

[Wagner1936-7] 1 2 Wagner, Klaus (1936), "Bemerkungen zum Vierfarbenproblem", Jahresbericht der Deutschen Mathematiker-Vereinigung , 46: 26–32

[8] Lawson, Charles L. (1972), "Transforming triangulations", Discrete Mathematics , 3: 365–372, doi: 10.1016/0012-365X(72)90093-3 , MR 0311491

[9] Santos, Francisco (2000), "A point set whose space of triangulations is disconnected", Journal of the American Mathematical Society , 13: 611–637, doi: 10.1090/S0894-0347-00-00330-1 , hdl: 10902/2584 , MR 1758756

[10] Santos, Francisco (2005), "Non-connected toric Hilbert schemes", Mathematische Annalen , 332: 645–665, arXiv: math/0204044 , doi:10.1007/s00208-005-0643-5, MR 2181765

[11] Pournin, Lionel (2013), "The flip-Graph of the 4-dimensional cube is connected", Discrete & Computational Geometry , 49: 511–530, arXiv: 1201.6543 , doi: 10.1007/s00454-013-9488-y , MR 3038527

[12] Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988). "Rotation distance, triangulations, and hyperbolic geometry". Journal of the American Mathematical Society. 1 (3): 647–681. doi: 10.1090/s0894-0347-1988-0928904-4 .

[13] Pournin, Lionel (2014). "The diameter of associahedra". Advances in Mathematics . 259: 13–42. arXiv: 1207.6296 . doi: 10.1016/j.aim.2014.02.035 . MR 3197650.

[14] Bose, Prosenjit; Verdonschot, Sander (2012). "A History of Flips in Combinatorial Triangulations". Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg. p. 29–44. doi:10.1007/978-3-642-34191-5_3. ISBN 978-3-642-34190-8. ISSN 0302-9743.

[15] Frati, Fabrizio (2017). "A Lower Bound on the Diameter of the Flip Graph". Electronic Journal of Combinatorics. 24 (1): P1.43. arXiv: 1508.03473 . doi: 10.37236/5489 .

[16] Parlier, Hugo; Pournin, Lionel (2017). "Flip-graph moduli spaces of filling surfaces". Journal of the European Mathematical Society . 19 (9): 2697–2737. arXiv: 1407.1516 . doi: 10.4171/JEMS/726 .

[17] Parlier, Hugo; Pournin, Lionel (2018). "Modular flip-graphs of one holed surfaces". European Journal of Combinatorics . 67: 158–173. arXiv: 1510.07664 . doi: 10.1016/j.ejc.2017.07.003 .

[18] Parlier, Hugo; Pournin, Lionel (2018). "Once punctured disks, non-convex polygons, and pointihedra". Annals of Combinatorics . 22 (3): 619–640. arXiv: 1602.04576 . doi:10.1007/s00026-018-0393-1.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]