graph.algorithms.connectivity

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

java.lang.Object

graph.algorithms.connectivity.PlanarAugmentation<V,E>

Type Parameters:

V - The vertex type

E - The edge type

public class PlanarAugmentation<V extends Vertex,E extends Edge<V>>
extends java.lang.Object

Given a connected, but not biconnected planar graph, the algorithm adds a minimum number of edges to turn it into a biconnected graph while not ruining the planarity This implementation is based on Fialko and Mutzel's 5/3 approximation

Author:

Renata

Constructor Summary

Constructors

Constructor and Description
PlanarAugmentation()

Method Summary

Modifier and Type	Method and Description
java.util.List<E>	planarBiconnected(Graph<V,E> graph) Finds edges which need to be added in order to transform the graph into a planar biconnected one.

Methods inherited from class java.lang.Object

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

Constructor Detail

PlanarAugmentation

public PlanarAugmentation()

Method Detail

planarBiconnected

public java.util.List<E> planarBiconnected(Graph<V,E> graph)
                                    throws CannotBeAppliedException

Finds edges which need to be added in order to transform the graph into a planar biconnected one.

Parameters:

graph - Graph that should be connected and planar that is to be turned into a biconnected graph

Returns:

Edges to be added

Throws:

CannotBeAppliedException - if the planar augmentation algorithm cannot be applied (graph is not planar or is not connected)