 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
PlanarityTestingAlgorithm<V,
E>
isPlanar()
does spend time only on the planarity testing. All of the operations of this algorithm (testing,
embedding and Kuratowski subgraph extraction) run in linear time.
A planar graph is a graph, which can be drawn in twodimensional space without any of its edges crossing. According to the Kuratowski theorem, a graph is planar if and only if it doesn't contain a subdivision of the $K_{3,3}$ or $K_{5}$ graphs.
The BoyerMyrvold planarity testing algorithm was originally described in: Boyer, John amp; Myrvold, Wendy. (2004). On the Cutting Edge: Simplified O(n) Planarity by Edge Addition. J. Graph Algorithms Appl.. 8. 241273. 10.7155/jgaa.00091. . We refer to this paper for the complete description of the BoyerMyrvold algorithm
 Author:
 Timofey Chudakov

Nested Class Summary
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.PlanarityTestingAlgorithm
PlanarityTestingAlgorithm.Embedding<V,
E>, PlanarityTestingAlgorithm.EmbeddingImpl<V, E> 
Constructor Summary
ConstructorDescriptionBoyerMyrvoldPlanarityInspector
(Graph<V, E> graph) Creates new instance of the planarity testing algorithm for thegraph
. 
Method Summary
Modifier and TypeMethodDescriptionComputes combinatorial embedding of the inputgraph
.Extracts a Kuratowski subdivision from thegraph
.boolean
isPlanar()
Tests the planarity of thegraph
.

Constructor Details

BoyerMyrvoldPlanarityInspector
Creates new instance of the planarity testing algorithm for thegraph
. The input graph can't be null. Parameters:
graph
 the graph to test the planarity of


Method Details

isPlanar
public boolean isPlanar()Tests the planarity of thegraph
. Returns true if the input graph is planar, false otherwise. If this method returns true, the combinatorial embedding of thegraph
is provided after the call to thePlanarityTestingAlgorithm.getEmbedding()
. Otherwise, a Kuratowski subdivision is provided after the call to thePlanarityTestingAlgorithm.getKuratowskiSubdivision()
.Only the first call to this method does the actual computation, all subsequent calls only return the previously computed value.
 Specified by:
isPlanar
in interfacePlanarityTestingAlgorithm<V,
E>  Returns:
true
if thegraph
is planar, false otherwise

getEmbedding
Computes combinatorial embedding of the inputgraph
. This method will return a valid result only if thegraph
is planar. For more information on the combinatorial embedding, seePlanarityTestingAlgorithm.Embedding
Only the first call to this method does the actual computation, all subsequent calls only return the previously computed value.
 Specified by:
getEmbedding
in interfacePlanarityTestingAlgorithm<V,
E>  Returns:
 combinatorial embedding of the input
graph

getKuratowskiSubdivision
Extracts a Kuratowski subdivision from thegraph
. The returned value certifies the nonplanarity of the graph. The returned certificate can be verified through the call to theGraphTests.isKuratowskiSubdivision(Graph)
. This method will return a valid result only if thegraph
is not planar.Only the first call to this method does the actual computation, all subsequent calls only return the previously computed value.
 Specified by:
getKuratowskiSubdivision
in interfacePlanarityTestingAlgorithm<V,
E>  Returns:
 a Kuratowski subdivision from the
graph
