Planarity Testing
A graph is called planar if it can be drawn in the plane without
edge crossings. In a drawing of a graph, nodes are identified with points
in the plane and edges with lines connecting the corresponding end nodes.
The edges are not allowed to cross nodes in the drawing.
A planar embedding represents a class of planar drawings. Given
a planar embedding planar drawings of the graph can be easily constructed.
Interesting Fact 1: A famous theorem by Kuratowski states that
a graph is planar if and only if it does not contain special subgraphs,
called Kuratowski subgraphs. Therefore, to test a graph for planarity
it is not necessary to really draw the graph.
Interesting Fact 2: A planar graph G=(V,E) (without
parallel edges and selfloops) can have at most 3|V|-6 edges.
LEDA Functions for Planarity Testing
PLANAR() checks in time O(|V|) if a graph G=(V,E)
is planar. It is also possible to compute a planar embedding with PLANAR().
If the given graph is not planar, a Kuratowski subgraph can be computed.
CHECK_KURATOWSKI() checks if a list<edge>
forms a Kuratowski subgraph of G. This function can be used
to check the result of PLANAR().
KURATOWSKI() computes a Kuratowski subdivision K
of G. Details can be found on the Manual
Page Algorithms for Planar Graphs.
Example of
How To Use PLANAR() and CHECK_KURATOWSKI()
Correctness of Planarity Testing
We provide the function PLANAR() for testing the planarity
of a graph and the independent test function CHECK_KURATOWSKI()
for the following reasons. The algorithms for planarity testing are very
complicated. Therefore, it is very difficult to ensure the correctness
of the implementation directly. In contrast, checking the planarity of
a graph with a Kuratowski subgraph is easy. The implementation of this
test is straightforward.
Using PLANAR() and CHECK_KURATOWSKI() together
increases the reliability of the result in case PLANAR()
returns false, that is, G is not planar.
In case PLANAR() returns true, that is, it
says that G is planar, we can use a drawing
algorithm for planar graphs and check visually that G
is planar.
|