LEDA Guide: Example Planarity Testing

Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Algorithms for Planar Graphs > Planarity Testing > Example

Example Planarity Testing

The following program shows how the functions PLANAR() and CHECK_KURATOWSKI() can be used to test the planarity of a given graph and check the correctness of the planarity test.

Remarks:

The graph algorithms in LEDA are generic, that is, they accept graphs as well as parameterized graphs.
The graph must not contain selfloops for PLANAR() to perform correctly.
There is a variant of PLANAR() that does not compute a Kuratowski subgraph. Both variants can also compute a planar embedding of G.

We first create a complete graph G with ten nodes (and 45 edges). Then we call PLANAR() for G and a list<edge> kuratowski_subgraph. If PLANAR() returns false, kuratowski_subgraph contains edges forming a Kuratowski subgraph of G which proves that G is not planar.

We use CHECK_KURATOWSKI() to check if kuratowski_subgraph really forms a Kuratowski subgraph of G. If CHECK_KURATOWSKI() returns false for a graph G and a list<edge> computed by PLANAR() we are in trouble, because PLANAR() did not work correctly. Otherwise, we can be sure that G is not PLANAR.

In case PLANAR() returns true, G is planar and kuratowski_subgraph is empty. If we want to check this result we can draw the graph using a graph drawing algorithm and examine the result visually. In our example we simply print "G is planar!".

#include <LEDA/graph/graph.h>
#include <LEDA/core/list.h>
#include <LEDA/graph/plane_graph_alg.h>

using namespace leda;

int main()
{
  graph G; 

  complete_ugraph(G,10);

  list<edge> kuratowski_subgraph;
  bool G_is_planar=PLANAR(G,kuratowski_subgraph);

  if (!G_is_planar) {
    bool is_kuratowski=CHECK_KURATOWSKI(G,kuratowski_subgraph);
    if (!is_kuratowski) {
      std::cout << "Problem in PLANAR()!" << std::endl;
      std::cout << "Not a Kuratowski subgraph!" << std::endl;
    }

    else std::cout << "Graph is not planar!" << std::endl;
  }

  else std::cout << "Graph is planar!" << std::endl;

  return 0;
}

Example Planarity Testing

See also: