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?

enter image description here

  • 1
    $\begingroup$ 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. $\endgroup$
    – Discrete lizard
    May 18, 2019 at 17:03
  • 1
    $\begingroup$ 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 $\endgroup$
    – HEKTO
    May 19, 2019 at 15:30
  • $\begingroup$ Are the motions of your vertices discrete jumps or continuous? $\endgroup$
    – John
    May 20, 2019 at 11:17
  • $\begingroup$ @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. $\endgroup$
    – JD.
    May 20, 2019 at 14:23
  • 1
    $\begingroup$ 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 $\endgroup$
    – HEKTO
    May 20, 2019 at 18:44


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.