Another particular interesting representation is Guibas and Stolfi's "quadedge" data structure from their 1985 paper at "Primitives for the manipulation of general subdivisions and the computation of Voronoi," source http://dl.acm.org/citation.cfm?doid=282918.282923 and pdf at http://www.sccg.sk/~samuelcik/dgs/quad_edge.pdf.

It really is an elegant use of some basic topology with impressive results, a full Voronoi/Delaunay linear-log time algorithm in less than a page of easily implementable pseudocode (once the data structure is written).