Abstract: In this paper we propose a new structure, star-vertex, to represent general planar meshes. The basic concept is simple, allowing constant adjacency query time, and scalability (ability to trade size for speed), and under specific situations requiring less storage space than others. For simplicity, we use a generic traverse element, which resembles the behavior of oriented edges. We present implementation examples of the proposed structure and comparisons with other mesh representation schemes.