st-Numbering
A graph is called planar if it can be drawn in the plane without
edge crossings. In a drawing of a graph, nodes are identified with points
in the plane and edges with lines connecting the corresponding end nodes.
The edges are not allowed to cross nodes in the drawing.
Given an biconnected graph
G=(V,E) and an edge e=(s,t) in E,
an st-numbering of G is a numbering of the nodes of
G with the following properties:
s has number 1, t has number |V|, and - every node different from
s and t has a
neighbor with a smaller and a neighbor with a larger number.
LEDA Function for st-Numbering
ST_NUMBERING() computes an st-numbering of
a given biconnected graph G=(V,E) in time O(|V|+|E|). An
st-numbering is used in the planarity
test.
Example of How To Use ST_NUMBERING()
The following program shows how the function ST_NUMBERING()
can be used on a biconnected graph.
Remark: The graph algorithms in LEDA are generic, that is, they
accept graphs as well as parameterized
graphs.
In main() we first create a biconnected, planar graph
G with four nodes and five edges. The edge from n0
to n3 is the edge marking s and t.
The result of ST_NUMBERING() is a node_array<int>
stnum containing for each node its st-number and a list<node>
stlist containing the nodes of G in the order of the
st-numbering.
#include <LEDA/graph/graph.h>
#include <LEDA/core/list.h>
#include <LEDA/graph/node_array.h>
#include <LEDA/graph/plane_graph_alg.h>
using namespace leda;
int main()
{
graph G;
node n0=G.new_node(); node n1=G.new_node();
node n2=G.new_node(); node n3=G.new_node();
edge e_st=G.new_edge(n0,n3);
G.new_edge(n0,n1); G.new_edge(n2,n0);
G.new_edge(n2,n3); G.new_edge(n3,n1);
node_array<int> stnum(G);
list<node> stlist;
ST_NUMBERING(G,stnum,stlist);
std::cout << "stnum:" << std::endl;
node v;
forall_nodes(v,G) {
G.print_node(v);
std::cout << " " << stnum[v] <
|