On "partial planarization" I understand an algorithm, which tries to reach an optimal, or nearly-optimal solution for non-planar graphs. For example, which minimizes the number of the crossing edges (but I can imagine some other viewpoint, too).

I think, a such algorithm could be maybe even fast (around $O(V^3)$ or maybe faster).

Is there a such algorithm?

  • 2
    $\begingroup$ What research have you done? Have you done a literature search? What's the best algorithm you've found so far? (Incidentally, $O(3)$ doesn't make sense.) $\endgroup$ – D.W. May 19 '15 at 22:51
  • $\begingroup$ @D.W. My actual self-invented algorithm places the edges in decreasing order by their degree. After that, there are some not really complex herustics (f.e. very "bad" scenarios are rolled back and restarted in another placement order). Currently, it is not really effective (it is in javascript which is slow and the results look bad). I would be glad to insert its details here, but I think it would be offtopic. Sorry for the $O()$ typo. $\endgroup$ – peterh May 20 '15 at 1:37
  • 1
    $\begingroup$ Have you consulted Wikipedia? en.wikipedia.org/wiki/Crossing_number_(graph_theory)#Complexity $\endgroup$ – Yuval Filmus May 20 '15 at 3:35
  • $\begingroup$ @YuvalFilmus Yes, but thank you very much your link. Unfortunately, finding the crossing is NP-Hard, and mostly I've found complex, but slow algorithms everywhere. My goal would be to find a fast (and maybe more simple) algorithm, in exchange it wouldn't be a problem if the solution would be only nearly-optimal. For example, it wouldn't be needed to find an optimal planarization, a nearly-optimal would be also enough. $\endgroup$ – peterh May 20 '15 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.