Abstract: In a broad range of computer graphics applications, the representation of geometric shape is based on triangle meshes. General purpose data structures for polygonal meshes typically provide fast access to geometric objects (e.g., points) and topological entities (e.g., neighborhood relationships) but the memory requirements are rather high due to the many special configurations. In this paper, we present a new data structure which is specifically designed for triangle meshes. The data structure enables the programmer to trade memory for access time by either storing internal references explicitly, or by reconstructing them locally on demand. The trade-off can be hidden from the programmer by an object-oriented API and can automatically adapt to the available hardware resources or the complexity of the mesh (scalability).