A triangulation is a planar straight line graph to which no more edges may be added, so called because every face is necessarily a triangle; a special case of this is the Delaunay triangulation, a graph defined from a set of points in the plane by connecting two points with an edge whenever there exists a circle containing only those two points.
A Levi graph of a family of points and lines has a vertex for each of these objects and an edge for every incident point-line pair.
An important special case of a partial cube is the skeleton of the permutohedron, a graph in which vertices represent permutations of a set of ordered objects and edges represent swaps of objects adjacent in the order.
It is also possible to define related flip graphs for partitions into quadrilaterals or pseudotriangles, and for higher-dimensional triangulations.
The flip graph of triangulations of a convex polygon forms the skeleton of the associahedron or Stasheff polytope.
The flip graph of the regular triangulations of a point set (projections of higher-dimensional convex hulls) can also be represented as a skeleton, of the so-called secondary polytope.