graph.algorithms.planarity

Class BoyerMyrvoldPlanarity<V extends Vertex,E extends Edge<V>>

java.lang.Object

graph.algorithms.planarity.PlanarityTestingAlgorithm<V,E>

graph.algorithms.planarity.BoyerMyrvoldPlanarity<V,E>

Type Parameters:

V - The vertex type

E - The edge type

public class BoyerMyrvoldPlanarity<V extends Vertex,E extends Edge<V>>
extends PlanarityTestingAlgorithm<V,E>

Implementation of the Boyer-Myrvold planarity testing algorithm The Boyer-Myrvold algorithm is a planarity testing algorithm which uses reverse DFS order as numbering of the vertices of G. The general strategy is that of explicitly maintaining a "flexible" planar embedding of each connected component of Gi with the outer vertices on the outer face. This embedding is "flexible" in the sense that each block can be flipped in constant time, whatever its size, while the permutation of the blocks around cutvertices is left undecided.

Author:

Renata

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	BoyerMyrvoldPlanarity.Block Represents a block used during the implementation of Boyer-Myrvold algorithm

Constructor Summary

Constructors

Constructor and Description
BoyerMyrvoldPlanarity()

Method Summary

Modifier and Type	Method and Description
java.util.List<E>	getExternalFaceEdges() Return edges of the outside face
java.util.List<V>	getOutsideFace() Return vertices of the outside face
boolean	isPlannar(Graph<V,E> graph) Determines if the graph is planar

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BoyerMyrvoldPlanarity

public BoyerMyrvoldPlanarity()

Method Detail

isPlannar

public boolean isPlannar(Graph<V,E> graph)

Description copied from class: PlanarityTestingAlgorithm

Determines if the graph is planar

Specified by:

isPlannar in class PlanarityTestingAlgorithm<V extends Vertex,E extends Edge<V>>

Parameters:

graph - Graph whose planarity is being checked

Returns:

true if graph is planar, otherwise false

getOutsideFace

public java.util.List<V> getOutsideFace()

Return vertices of the outside face

Returns:

A list of vertices forming the outside face

getExternalFaceEdges

public java.util.List<E> getExternalFaceEdges()

Return edges of the outside face

Returns:

A list of edges forming the outside face