ogdf::UpwardPlanarity Class Reference

Upward planarity testing and embedding. More...

#include <ogdf/upward/UpwardPlanarity.h>

Static Public Member Functions
General digraphs
static bool	isUpwardPlanar (Graph &G)
	Tests whether graph G is upward planar (using satisfiability).
static bool	embedUpwardPlanar (Graph &G, adjEntry &externalToItsRight)
	Tests whether graph G is upward planar and embeds the graph by a upward planar embedding if possible (using satisfiability).
Biconnected digraphs
static bool	isUpwardPlanar_embedded (const Graph &G)
	Tests whether a biconnected graph G is upward planarly embedded.
static bool	isUpwardPlanar_embedded (const Graph &G, List< adjEntry > &possibleExternalFaces)
	Tests whether a biconnected graph G is upward planarly embedded and computes the set of possible external faces.
Triconnected digraphs
static bool	isUpwardPlanar_triconnected (const Graph &G)
	Tests whether the triconnected digraph G is upward planar.
static bool	upwardPlanarEmbed_triconnected (Graph &G)
	Upward planarly embeds the triconnected digraph G.
Single-source digraphs
static bool	isUpwardPlanar_singleSource (const Graph &G)
	Tests whether the single-source digraph G is upward planar.
static bool	upwardPlanarEmbed_singleSource (Graph &G)
	Upward planarly embeds the single-source digraph G.
static bool	upwardPlanarAugment_singleSource (Graph &G)
	Tests whether single-source digraph G is upward planar, and if yes augments it to a planar st-digraph.
static bool	upwardPlanarAugment_singleSource (Graph &G, node &superSink, SList< edge > &augmentedEdges)
	Tests whether single-source digraph G is upward planar, and if yes augments it to a planar st-digraph.
static bool	isUpwardPlanar_singleSource_embedded (const ConstCombinatorialEmbedding &E, SList< face > &externalFaces)
	Tests whether the embedding E of a single-source digraph is upward planar.
static bool	upwardPlanarAugment_singleSource_embedded (Graph &G, node &superSink, SList< edge > &augmentedEdges)
	Tests if single-source digraph G is upward planarly embedded and augments it to a planar st-digraph.

Detailed Description

Upward planarity testing and embedding.

This class provides various static functions for upward planarity testing and embedding. These functions perform different tasks (testing, embedding, augmenting) and pose different restrictions on the input graph (general, biconnected, single source).

We use a strict naming scheme to make it clear what the functions are doing and which restrictions they have. The prefix of the function name denotes the task:

• isUpwardPlanar: Tests if the input graph is upward planar.
• upwardPlanarEmbed: First tests if the input graph is upward planar, and if yes upward planarly embeds it.
• upwardPlanarAugment: Adds additional edges to the input graph such that the graph remains upward planar and fulfills a special property like single source.

The suffix of the function name (if present) describes additional restrictions:

• singleSource: The input graph has exactly one source (but possibly several sinks).
• seriesParallel: The input graph is a series-parallel graph.

Some of the functions take a combinatorial embedding (e.g., given by the order in the adjacency lists) as input and test this given embedding. These functions are appended by _embedded.

Definition at line 72 of file UpwardPlanarity.h.

Member Function Documentation

embedUpwardPlanar()

static bool ogdf::UpwardPlanarity::embedUpwardPlanar ( Graph &  G, adjEntry &  externalToItsRight  )

static

Tests whether graph G is upward planar and embeds the graph by a upward planar embedding if possible (using satisfiability).

Parameters

G	is the input graph to be embedded if it allows an upward planar embedding.
externalToItsRight	indicates the external face (on its right side)

Returns

true if G is upward planar, false otherwise.

isUpwardPlanar()

static bool ogdf::UpwardPlanarity::isUpwardPlanar ( Graph &  G )

static

Tests whether graph G is upward planar (using satisfiability).

Parameters

G	is the input graph to be tested.

Returns

true if G is upward planar, false otherwise.

isUpwardPlanar_embedded() [1/2]

static bool ogdf::UpwardPlanarity::isUpwardPlanar_embedded ( const Graph &  G )

static

Tests whether a biconnected graph G is upward planarly embedded.

The fixed embedding of G is given by the order of G's adjacency lists.

Parameters

G	is the input graph to be tested.

Returns

true if G is upward planarly embedded, false otherwise.

isUpwardPlanar_embedded() [2/2]

static bool ogdf::UpwardPlanarity::isUpwardPlanar_embedded ( const Graph &  G, List< adjEntry > &  possibleExternalFaces  )

static

Tests whether a biconnected graph G is upward planarly embedded and computes the set of possible external faces.

isUpwardPlanar_singleSource()

static bool ogdf::UpwardPlanarity::isUpwardPlanar_singleSource ( const Graph &  G )

static

Tests whether the single-source digraph G is upward planar.

Remarks

If G is not single-source the function returns false.

Parameters

G	is the (single-source) input digraph.

Returns

true if G was single-source and upward planar, false otherwise.

isUpwardPlanar_singleSource_embedded()

static bool ogdf::UpwardPlanarity::isUpwardPlanar_singleSource_embedded ( const ConstCombinatorialEmbedding &  E, SList< face > &  externalFaces  )

static

Tests whether the embedding E of a single-source digraph is upward planar.

Parameters

E	is the given combinatorial embedding to be tested.
externalFaces	is assigned the list of possible external faces such that E is upward planar.

Returns

true if E is upward planar, false otherwise.

isUpwardPlanar_triconnected()

static bool ogdf::UpwardPlanarity::isUpwardPlanar_triconnected ( const Graph &  G )

static

Tests whether the triconnected digraph G is upward planar.

Remarks

If G is not triconnected the function returns false.

Parameters

G	is the (triconnected) input digraph.

Returns

true if G was triconnected and upward planar, false otherwise.

upwardPlanarAugment_singleSource() [1/2]

static bool ogdf::UpwardPlanarity::upwardPlanarAugment_singleSource ( Graph &  G )

static

Tests whether single-source digraph G is upward planar, and if yes augments it to a planar st-digraph.

Remarks

If G is not single-source the function returns false.

If G is upward planar, this method adds a super sink node t and adds further edges such that the resulting digraph is a planar st-digraph.

Parameters

G	is the input digraph which gets augmented.

Returns

true if G is single-source and upward planar, false otherwise.

upwardPlanarAugment_singleSource() [2/2]

static bool ogdf::UpwardPlanarity::upwardPlanarAugment_singleSource ( Graph &  G, node &  superSink, SList< edge > &  augmentedEdges  )

static

Tests whether single-source digraph G is upward planar, and if yes augments it to a planar st-digraph.

Remarks

If G is not single-source the function returns false.

If G is upward planar, this method adds a super sink node superSink and adds further edges such that the resulting digraph is a planar st-digraph.

Parameters

G	is the input digraph which gets augmented.
superSink	is assigned the inserted super sink node.
augmentedEdges	is assigned the list of inserted edges.

Returns

true if G is single-source and upward planar, false otherwise.

upwardPlanarAugment_singleSource_embedded()

static bool ogdf::UpwardPlanarity::upwardPlanarAugment_singleSource_embedded ( Graph &  G, node &  superSink, SList< edge > &  augmentedEdges  )

static

Tests if single-source digraph G is upward planarly embedded and augments it to a planar st-digraph.

Parameters

G	is the embedded input graph.
superSink	is assigned the added super sink.
augmentedEdges	is assigned the list of added edges.

Returns

true if G is upward planarly embedded (in this case G is also augmented by adding a super sink and additional edges), false otherwise.

upwardPlanarEmbed_singleSource()

static bool ogdf::UpwardPlanarity::upwardPlanarEmbed_singleSource ( Graph &  G )

static

Upward planarly embeds the single-source digraph G.

Remarks

If G is not single-source the function returns false.

Parameters

G	is the (single-source) input digraph.

Returns

true if G was single-source and upward planar, false otherwise.

upwardPlanarEmbed_triconnected()

static bool ogdf::UpwardPlanarity::upwardPlanarEmbed_triconnected ( Graph &  G )

static

Upward planarly embeds the triconnected digraph G.

Remarks

If G is not triconnected the function returns false.

Parameters

G	is the (triconnected) input digraph.

Returns

true if G was triconnected and upward planar, false otherwise.

---

The documentation for this class was generated from the following file:

• include/ogdf/upward/UpwardPlanarity.h