# OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

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. More...

bool ogdf::isSTPlanar (const Graph &graph, const node s, const node t)
Returns whether G is s-t-planar (i.e. More...

bool ogdf::planarEmbed (Graph &G)
Returns true, if G is planar, false otherwise. If true is returned, G will be planarly embedded. More...

bool ogdf::planarEmbedPlanarGraph (Graph &G)
Constructs a planar embedding of G. It assumes that G is planar! More...

bool ogdf::planarSTEmbed (Graph &graph, node s, node t)
s-t-planarly embeds a graph. More...

## Detailed Description

Algorithms for testing planarity and for planar embedding of graphs.

## ◆ 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 441 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 456 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 481 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 520 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 496 of file extended_graph_alg.h.