You might want to look at the partial entity structure, described by S. Lee and K. Lee. It is designed for nonmanifold meshes, and if I recall correctly, has roughly half the memory requirement of the half edge structure. Matt