Return to Question

A planar graph is a graph that can be drawn in the plane such that no two edges cross.

For example, the graph Graph[{{1, 2}, {2, 3}, {3, 1}, {1, 4}, {3, 4}, {2, 4}}] is planar, and can be shown in both of these ways:

The layout in the left doesn't have crossing edges and it's immediately obvious that the graph is planar. The layout on the right is what Mathematica gives me by default.

Question: How can a planar graph be shown without any crossing edges in Mathematica?

I expect Combinatorica` might have this feature as it has a PlanarQ function, but unfortunately the documentation is not included with Mathematica and I have not been able to find out how to do this.

Testing whether a Graph is planar is possible like this:

<< GraphUtilities` PlanarQ@ToCombinatoricaGraph[someGraph] 

Here's a random set of planar graph of different sizes to test on:

<< ComputationalGeometry` graphs = DeleteDuplicates[ Flatten@Table[ Graph@ Union[Sort /@ Join @@ (Thread /@ DelaunayTriangulation@RandomReal[1, {j, 2}])], {10}, {j, 4, 10} ], IsomorphicGraphQ]; 

To avoid confusion, I'd like to note that the ComputationalGeometry`PlanarGraphPlot[] function does not do what I need. It does not lay out a graph. One needs to provide an explicit list of vertex coordinates to it. I have a graph as the input, I know that it's planar, and need a layout algorithm that will draw the graph without intersecting edges.

A planar graph is a graph that can be drawn in the plane such that no two edges cross.

For example, the graph Graph[{{1, 2}, {2, 3}, {3, 1}, {1, 4}, {3, 4}, {2, 4}}] is planar, and can be shown in both of these ways:

The layout in the left doesn't have crossing edges and it's immediately obvious that the graph is planar. The layout on the right is what Mathematica gives me by default.

Question: How can a planar graph be shown without any crossing edges in Mathematica?

I expect Combinatorica` might have this feature as it has a PlanarQ function, but unfortunately the documentation is not included with Mathematica and I have not been able to find out how to do this.

Testing whether a Graph is planar is possible like this:

<< GraphUtilities` PlanarQ@ToCombinatoricaGraph[someGraph] 

Note: The above way of testing planarity is for version 8 or earlier. The PlanarGraphQ built-in function was introduced in version 9.

Here's a random set of planar graph of different sizes to test on:

<< ComputationalGeometry` graphs = DeleteDuplicates[ Flatten@Table[ Graph@ Union[Sort /@ Join @@ (Thread /@ DelaunayTriangulation@RandomReal[1, {j, 2}])], {10}, {j, 4, 10} ], IsomorphicGraphQ]; 

To avoid confusion, I'd like to note that the ComputationalGeometry`PlanarGraphPlot[] function does not do what I need. It does not lay out a graph. One needs to provide an explicit list of vertex coordinates to it. I have a graph as the input, I know that it's planar, and need a layout algorithm that will draw the graph without intersecting edges.

A planar graph is a graph that can be drawn in the plane such that no two edges cross.

For example, the graph Graph[{{1, 2}, {2, 3}, {3, 1}, {1, 4}, {3, 4}, {2, 4}}] is planar, and can be shown in both of these ways:

The layout in the left doesn't have crossing edges and it's immediately obvious that the graph is planar. The layout on the right is what Mathematica gives me by default.

Question: How can a planar graph be shown without any crossing edges in Mathematica?

I expect Combinatorica` might have this feature as it has a PlanarQ function, but unfortunately the documentation is not included with Mathematica and I have not been able to find out how to do this.

Testing whether a Graph is planar is possible like this:

<< GraphUtilities` PlanarQ@ToCombinatoricaGraph[someGraph] 

Here's a random set of planar graph of different sizes to test on:

<< ComputationalGeometry` graphs = DeleteDuplicates[ Flatten@Table[ Graph@ Union[Sort /@ Join @@ (Thread /@ DelaunayTriangulation@RandomReal[1, {j, 2}])], {10}, {j, 4, 10} ], IsomorphicGraphQ]; 

A planar graph is a graph that can be drawn in the plane such that no two edges cross.

For example, the graph Graph[{{1, 2}, {2, 3}, {3, 1}, {1, 4}, {3, 4}, {2, 4}}] is planar, and can be shown in both of these ways:

The layout in the left doesn't have crossing edges and it's immediately obvious that the graph is planar. The layout on the right is what Mathematica gives me by default.

Question: How can a planar graph be shown without any crossing edges in Mathematica?

I expect Combinatorica` might have this feature as it has a PlanarQ function, but unfortunately the documentation is not included with Mathematica and I have not been able to find out how to do this.

Testing whether a Graph is planar is possible like this:

<< GraphUtilities` PlanarQ@ToCombinatoricaGraph[someGraph] 

Here's a random set of planar graph of different sizes to test on:

<< ComputationalGeometry` graphs = DeleteDuplicates[ Flatten@Table[ Graph@ Union[Sort /@ Join @@ (Thread /@ DelaunayTriangulation@RandomReal[1, {j, 2}])], {10}, {j, 4, 10} ], IsomorphicGraphQ]; 

To avoid confusion, I'd like to note that the ComputationalGeometry`PlanarGraphPlot[] function does not do what I need. It does not lay out a graph. One needs to provide an explicit list of vertex coordinates to it. I have a graph as the input, I know that it's planar, and need a layout algorithm that will draw the graph without intersecting edges.