# DCEL with dynamic graph

Is doubly-connected edge list a good data-structure for planar graph which vertices can be moved freely?

I experienced DCEL as a very good structure when it comes to add/delete some vertex or edge. And I can detect all faces easily too. But when I start to move vertices of the graph it can happen that the graph is no longer valid.

Am I forced to reconstruct my whole graph from scratch every time I move one of vertices, because I could screw the topology of the graph?

Or is there any better data-structure for this purpouses?

• First note that what you describe (and have drawn) here is not a planar graph, but a planar subdivision that is an embedding of a planar graph. (A DCEL stores just that, a planar subdivision) What you need is an efficient algorithm to find the topology of your planar subdivision after moving vertices. That algorithm can use a data-structure appropriate for that task. I think that you can definitely do better than redrawing everything in most cases, although it might be nessecary in the worst case. May 18, 2019 at 17:03
• No need to reconstruct the whole graph - you can delete the $v_5$ and then reinsert it in a new position using point location algorithm to find a face, where it should be May 19, 2019 at 15:30
• Are the motions of your vertices discrete jumps or continuous?
– John
May 20, 2019 at 11:17
• @John It is kind of a CAD program so it is continuous. But I think I can simulate discrete jumps by rebuilding graph only on mouse release.
– JD.
May 20, 2019 at 14:23
• It's unclear, what you're trying to do in general - so please remember, that after this vertex deleting/reinserting you can get a plane subdivision, corresponding to a different planar graph May 20, 2019 at 18:44