Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Algorithms for Planar Graphs > 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;

  std::cout << "stnum:" << std::endl;
  node v; 
  forall_nodes(v,G) {
    std::cout << " " << stnum[v] <

See also:

Algorithms for Planar Graphs


Parameterized Graphs

Planarity Testing

Linear Lists

Node Arrays

Biconnected Components

Graph Algorithms

Graphs and Related Data Types

Manual Entries:

Manual Page Algorithms for Planar Graphs

Please send any suggestions, comments or questions to
© Copyright 2001-2003, Algorithmic Solutions Software GmbH