Pre-triangulations and liftable complexes

O. Aichholzer, F. Aurenhammer, and T. Hackl


We introduce the concept of pre-triangulations, a relaxation of triangulations that goes beyond the frequently used concept of pseudo-triangulations. Pre-triangulations turn out to be more natural than pseudo-triangulations in certain cases. We show that pre-triangulations arise in three different contexts: In the characterization of polygonal complexes that are liftable to three-space in a strong sense, in flip sequences for general polygonal complexes, and as graphs of maximal locally convex functions.

Reference: O. Aichholzer, F. Aurenhammer, and T. Hackl. Pre-triangulations and liftable complexes. Discrete & Computational Geometry, 38:701-725, 2007.