Interface PlanarityTestingAlgorithm<V,E>

Type Parameters:
V - the graph vertex type
E - the graph edge type
All Known Implementing Classes:
BoyerMyrvoldPlanarityInspector

public interface PlanarityTestingAlgorithm<V,E>
Allows to check the planarity of the graph. A graph is defined to be planar if it can be drawn on a two-dimensional plane without any of its edges crossing.
Author:
Timofey Chudakov
• Nested Class Summary

Nested Classes
Modifier and Type
Interface
Description
static interface
PlanarityTestingAlgorithm.Embedding<V,E>
A combinatorial embedding of the graph.
static class
PlanarityTestingAlgorithm.EmbeddingImpl<V,E>
• Method Summary

Modifier and Type
Method
Description
PlanarityTestingAlgorithm.Embedding<V,E>
getEmbedding()
Computes combinatorial embedding of the input graph.
Graph<V,E>
getKuratowskiSubdivision()
Extracts a Kuratowski subdivision from the graph.
boolean
isPlanar()
Tests the planarity of the graph.
• Method Details

• isPlanar

boolean isPlanar()
Tests the planarity of the graph. Returns true if the input graph is planar, false otherwise. If this method returns true, the combinatorial embedding of the graph is provided after the call to the getEmbedding(). Otherwise, a Kuratowski subdivision is provided after the call to the getKuratowskiSubdivision().
Returns:
true if the graph is planar, false otherwise
• getEmbedding

getEmbedding()
Computes combinatorial embedding of the input graph. This method will return a valid result only if the graph is planar. For more information on the combinatorial embedding, see PlanarityTestingAlgorithm.Embedding
Returns:
combinatorial embedding of the input graph
• getKuratowskiSubdivision

Graph<V,E> getKuratowskiSubdivision()
Extracts a Kuratowski subdivision from the graph. The returned value certifies the nonplanarity of the graph. The returned certificate can be verified through the call to the GraphTests.isKuratowskiSubdivision(Graph). This method will return a valid result only if the graph is not planar.
Returns:
a Kuratowski subdivision from the graph