Planarity Testing and Embedding

Algorithms for testing planarity and for planar embedding of graphs. More...

Classes
class	ogdf::BoothLueker
	Booth-Lueker planarity test. More...
class	ogdf::BoyerMyrvold
	Wrapper class used for preprocessing and valid invocation of the planarity test. More...
class	ogdf::EmbedderMaxFace
	Embedder that maximizes the external face. More...
class	ogdf::EmbedderMaxFaceLayers
	Embedder that maximizes the external face and optimizes the position of blocks afterwards. More...
class	ogdf::EmbedderMinDepth
	Embedder that minimizes block-nesting depth. More...
class	ogdf::EmbedderMinDepthMaxFace
	Embedding that minimizes block-nesting depth and maximizes the external face. More...
class	ogdf::EmbedderMinDepthMaxFaceLayers
	Planar graph embedding that minimizes block-nesting depth and maximizes the external face and optimizes the position of blocks afterwards. More...
class	ogdf::EmbedderMinDepthPiTa
	Embedder that minimizes block-nesting depth for given embedded blocks. More...
class	ogdf::EmbedderOptimalFlexDraw
	The algorithm computes a planar embedding with minimum cost. More...

Functions
bool	ogdf::isPlanar (const Graph &G)
	Returns true, if G is planar, false otherwise.
bool	ogdf::isSTPlanar (const Graph &graph, const node s, const node t)
	Returns whether G is s-t-planar (i.e.
bool	ogdf::planarEmbed (Graph &G)
	Returns true, if G is planar, false otherwise. If true is returned, G will be planarly embedded.
bool	ogdf::planarEmbedPlanarGraph (Graph &G)
	Constructs a planar embedding of G. It assumes that G is planar!
bool	ogdf::planarSTEmbed (Graph &graph, node s, node t)
	s-t-planarly embeds a graph.

Detailed Description

Algorithms for testing planarity and for planar embedding of graphs.

Function Documentation

isPlanar()

bool ogdf::isPlanar ( const Graph &  G )

inline

Returns true, if G is planar, false otherwise.

This is a shortcut for BoyerMyrvold::isPlanar().

Parameters

G	is the input graph.

Returns

true if G is planar, false otherwise.

Definition at line 403 of file extended_graph_alg.h.

isSTPlanar()

bool ogdf::isSTPlanar ( const Graph &  graph, const node  s, const node  t  )

inline

Returns whether G is s-t-planar (i.e.

it can be planarly embedded with s and t sharing a face).

Parameters

graph	The graph to be tested
s	The node to be incident to the same face as t nodes
t	The other node

Returns

true iff the graph is s-t-planar

Definition at line 416 of file extended_graph_alg.h.

planarEmbed()

bool ogdf::planarEmbed ( Graph &  G )

inline

Returns true, if G is planar, false otherwise. If true is returned, G will be planarly embedded.

This is a shortcut for BoyerMyrvold::planarEmbed

Parameters

G	is the input graph.

Returns

true if G is planar, false otherwise.

Definition at line 437 of file extended_graph_alg.h.

planarEmbedPlanarGraph()

bool ogdf::planarEmbedPlanarGraph ( Graph &  G )

inline

Constructs a planar embedding of G. It assumes that G is planar!

This routine is slightly faster than planarEmbed(), but requires G to be planar. If G is not planar, the graph will be destroyed while trying to embed it!

This is a shortcut for BoyerMyrvold::planarEmbedPlanarGraph().

Parameters

G	is the input graph.

Returns

true if the embedding was successful; false, if the given graph was non-planar (in this case the graph will be left in an at least partially deleted state).

Definition at line 472 of file extended_graph_alg.h.

planarSTEmbed()

bool ogdf::planarSTEmbed ( Graph &  graph, node  s, node  t  )

inline

s-t-planarly embeds a graph.

Parameters

graph	The graph to be embedded
s	The node to be incident to the same face as t nodes
t	The other node

Returns

true iff the graph was successfully embedded

Definition at line 450 of file extended_graph_alg.h.