node  ST_NUMBERING(const graph& G, node_array< int> & stnum, list< node> & stlist, edge e_st = nil)  
ST_NUMBERING computes an st
numbering of G
. If e_st is nil then
t
is set to some arbitrary node of G
. The node s
is set to a
neighbor of t
and is returned. If e_st is not nil then s
is set
to the source of e_st and t
is set to its target.
The nodes of G
are numbered such
that s
has number 1, t
has number n
, and every node v
different
from s
and t
has a smaller and a larger numbered neighbor.
The ordered list of nodes is returned in stlist. If G
has no nodes
then nil is returned and if G
has exactly one node then this node is returned and given number one. Precondition G is biconnected. 

bool  PLANAR(graph& , bool embed=false)  
PLANAR takes as input a directed graph G(V, E)
and performs a planarity test
for it. G
must not contain selfloops. If the second argument embed
has
value true
and G
is a planar
graph it is transformed into a planar map (a combinatorial embedding such that
the edges in all adjacency lists are in clockwise ordering). PLANAR returns
true if G
is planar and false otherwise.
The algorithm ([45]) has running time
O( V +  E)
.


bool  PLANAR(graph& G, list< edge> & el, bool embed=false)  
PLANAR takes as input a directed graph G(V, E)
and performs a planarity test
for G
. PLANAR returns true if G
is planar and false otherwise.
If G
is not planar a KuratowskySubgraph is computed and returned in el
.


bool  CHECK_KURATOWSKI(const graph& G, const list< edge> & el)  
returns true if all edges in el are edges of G and if the edges in el form a Kuratowski subgraph of G
, returns false otherwise. Writes diagnostic output to cerr.


int  KURATOWSKI(graph& G, list< node> & V, list< edge> & E, node_array< int> & deg)  
KURATOWKI computes a Kuratowski subdivision K
of G
as follows. V
is the
list of all nodes and subdivision points of K
. For all v V
the degree
deg[v]
is equal to 2 for subdivision points, 4 for all other nodes if K
is a K_{5}
, and 3 (+3) for the nodes of the left (right) side if K
is a
K_{3, 3}
. E
is the list of all edges in the Kuratowski subdivision.


list< edge>  TRIANGULATE_PLANAR_MAP(graph& G)  
TRIANGULATE_PLANAR_MAP takes a directed graph G
representing a planar map.
It triangulates the faces of G
by inserting additional edges. The list of
inserted edges is returned.
Precondition G must be connected. The algorithm ([47]) has running time O( V +  E) .


void  FIVE_COLOR(graph& G, node_array< int> & C)  
colors the nodes of G using 5 colors, more precisely, computes for every node v a color C[v] {0,..., 4} , such that C[source(e)]! = C[target(e)] for every edge e . Precondition G is planar. Remark: works also for many (sparse ?) nonplanar graph.  
void  INDEPENDENT_SET(const graph& G, list< node> & I)  
determines an independent set of nodes I in G . Every node in I has degree at most 9. If G is planar and has no parallel edges then I contains at least n/6 nodes.  
bool  Is_CCW_Ordered(const graph& G, const node_array< int> & x, const node_array< int> & y)  
checks whether the cyclic adjacency list of any node v agrees with the counterclockwise ordering of the neighbors of v around v defined by their geometric positions.  
bool  SORT_EDGES(graph& G, const node_array< int> & x, const node_array< int> & y)  
reorders all adjacency lists such the cyclic adjacency list of any node v agrees with the counterclockwise order of v 's neighbors around v defined by their geometric positions. The function returns true if G is a plane map after the call.  
bool  Is_CCW_Ordered(const graph& G, const edge_array< int> & dx, const edge_array< int> & dy)  
checks whether the cyclic adjacency list of any node v agrees with the counterclockwise ordering of the neighbors of v around v . The direction of edge e is given by the vector (dx(e), dy(e)) .  
bool  SORT_EDGES(graph& G, const edge_array< int> & dx, const edge_array< int> & dy)  
reorders all adjacency lists such the cyclic adjacency list of any node v agrees with the counterclockwise order of v 's neighbors around v . The direction of edge e is given by the vector (dx(e), dy(e)) . The function returns true if G is a plane map after the call. 