Open
Graph Drawing
Framework

 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.

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
Gis 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
graphThe graph to be tested
sThe node to be incident to the same face as t nodes
tThe 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
Gis 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
Gis 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
graphThe graph to be embedded
sThe node to be incident to the same face as t nodes
tThe other node
Returns
true iff the graph was successfully embedded

Definition at line 496 of file extended_graph_alg.h.