Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Algorithms for Planar Graphs > st-Numbering

## 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] <
```

Algorithms for Planar Graphs

Graphs

Parameterized Graphs

Planarity Testing

Linear Lists

Node Arrays

Biconnected Components

Graphs and Related Data Types

Manual Entries:

Manual Page Algorithms for Planar Graphs