javaalgorithmgraphplanar-graph

Algorithm to make a simple graph planar

I want to know there is some algorithm that make a graph into planar graph ? I searched in Google I didn't find something that can help me enter image description here

Solution

  • This is too long for a comment. So excuse me providing an answer.

    Your question is unclear to me. Whether a graph is planar is a function of the graph itself, not how it is drawn. "In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints." from http://en.wikipedia.org/wiki/Planar_graph).

    Do you need to work out/check if the graph is planar?

    Do you need to draw it in planar form?

    In the example you provide, why is the second drawing somehow more correct than the first drawing? Is it only because their are no intersecting edges?

    Assuming you need to do this with other graphs, what rule is used to determine whether some representation is better than some other, how does your diagram generalise to other graphs?

    Why are you doing this? What is the point? If its homework, what exactly is the problem statement? If its real-life, maybe an explanation of what you are really trying to do would help.