Geek Answers Handbook

Algorithm for Planarizing a Non-Planar Graph

Is there a popular algorithm for planarizing a non-planar graph.

I am currently planning to implement the Orthogonal Planar Layout algorithm for undirected graphs in Boost (Boost Graph Library). BGL has an implementation for checking the planarity of an undirected graph (Boyer-Myrvold planetary testing), and I plan to use the flat embedding returned by this method for an orthogonal layout.

But I'm not sure what to do if the input graph is unplanar. Do I have to do something with the Kuratovsky subgraph returned in such a scenario to make the graph flat.

A Google search for "Planarization of non-planar graphs" returns several research papers. I'm not sure where to start.

+4
source share
1 answer

There are exponentially many $ K_5 $ and $ K_ {3,3} $ subgraphs $ K_n $, not paying attention to minors, so their appeal directly is not very effective. I suggest flipping through research papers to learn a little about how other people approach this problem. You should pay attention to the properties that (a) give reasonable solutions and (b) sound like the graphics you are interested in.

+1
source

More articles:


All Articles