I need to implement an algorithm that works on planar graphs and I want to select an appropriate data structure to represent them.
The vertices are stored in an array, each with an associated pair of coordinates,
An edge has an associated polyline between its end vertices, with an arbitrary number of intermediate points (possibly none), stored in sequence in an auxiliary array.
The edges are undirected (if $a\to b$ exists, then $b\to a$ exists),
The following primitive operations must be supported:
adding an edge between two vertices designated by their indexes,
enumerating all edges originating from a given vertex (and recursively, all paths from a given vertex),
for a given edge, follow the associated polyline until the end vertex.
I am looking for a data structure that is space efficient $O(V + E)$ and avoids data redundancy.
What would you use ? Candidates that I see are adjacency lists, DCEL, winged edges, but I may be missing one. I guess that quad edges is overkill.