Algorithm to make a simple graph planar

Question

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

Answer 1

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.

Answer 2

There is an Eulers Theorem that applies to every planar graph.

Definiton: A Planar Graph is a graph that can be drawn on the plane so that the edges do not cross each other. Any planar graph partitions the plane into a number of disjoint regions called the faces of the graph.

Euler's Theorem: V-E+F=2 where:

1. – V is the number of vertices,
2. – E is the number of edges,
3. – F is the number of faces

However, I can not provide a solution in java since its not clear the way you want to implement that. For instance, if you want to transform a graph into planar graph; visually, you might need a canvas and elements rearrangement, which will be kind of complicated to implement. In general think algorithmic wise, creating the solution first in pseudocode.

For example, since we have Euler's theorem that applies to every planar graph, you need to find a way to apply this theorem to your existing non planar graph and then test it.

Steps: (probably some of them will require coordinates)

• Determine what are the vertices
• Determine what are the edges
• Determine what are the faces
• Find a way to count the vertices
• Find a way to count the edges
• Find a way to count the faces
• Rearrange all those in a canvas
• Test the theorem, if it applies then your graph is planar, otherwise, rearrange again.
• Note that, by the use of coordinates you can determine from the beginning if the graph can be drawn planar, however, when you draw it you should not allowed any line edges to cross.