The Canonical Ordering of a Graph ( CanonicalOrder )

Definition

An instance C of type CanonicalOrder is canonical ordering of a plane graph G=(V,E). It represents an ordered partition V₁,..., V_m of V. We provide a canonical ordering for triconnected planar graphs (Goos Kant), and another one for biconnected planar graphs:

Definition (canonical ordering for triconnected planar graphs): Let G = (V, E) be a triconnected plane graph with | V| > = 3, outerface F_out, and v₁,..., v_q a path on F_out with q < | F_out|. Let C = V₁,..., V_m be an ordered partition of V, that is, V₁ $\cup$...$\cup$ V_m = V and V_i $\cap$ V_j = $\emptyset$ for i! = j. Define G_k to be the subgraph of G induced by V₁ $\cup$...$\cup$ V_k, and denote by C_k the outerface of G_k. C is a canonical ordering (for triconnected planar graphs) of G with base v₁,..., v_q if:

• V₁ = {v₁,..., v_q}
• V_m = {z₀}, where z₀ lies on the outerface of G.
• Each C_k (k > 1) is a cycle containing v₁,..., v_q.
• Each G_k is biconnected and internally triconnected, that is, removing two internal vertices of G_k does not disconnect it.
• For each k in {2,..., m - 1}, one of the following conditions holds:
  1. V_k = {z}, where z belongs to C_k and has at least one neighbour in G $\setminus$ G_k.
  2. V_k is a chain, (z₁,..., z_p), where each z_i has at least one neighbour in G $\setminus$ G_k, and where z₁ and z_p each have one neighbour on C_{k - 1}, and these are the only two neighbours of V_k in G_{k - 1}.

This is the definition of the canonical ordering for triconnected planar graphs by Goos Kant extended by the possibility to have more than two nodes in V₁.

Definition (canonical ordering for biconnected planar graphs): Let G = (V, E) be a biconnected plane graph with | V| > = 2, outerface F_out and v₁,..., v_q a path on F_out with (v_i, v_j)$\notin$E for all j! = i + 1. Let C = (V₁,..., V_m) be an ordered partition of V, that is, V₁ $\cup$...$\cup$ V_m = V and V_i $\cap$ V_j = $\emptyset$ for i! = j. Define G_k to be the subgraph of G induced by V₁ $\cup$ V₂...$\cup$ V_k, and denote by C_k the outerface of G_k. C is a canonical ordering (for biconnected planar graphs) of G with base v₁,..., v_q if:

• V₁ = {v₁,..., v_q}
• Each C_k (k > 1) is a cycle containing v₁,..., v_q.
• Each G_k is connected and internally biconnected, that is, removing one internal vertex of G_k does not disconnect it.
• For each k in {2,..., m - 1} holds:
  Each z $\in$ V_k belongs to C_k, and one of the following conditions holds, where C_{k - 1} = (v₁ = c₁,..., c_q = v₂):
  1. V_k = {z} and z has at least two neighbours in G_{k - 1}.
  2. V_k is a chain (z₁,...z_p) with p > = 1 of vertices with degree $\le$2 in G_k, and there are two vertices c_$\ell$ and c_r (1 < = $\ell$ < r < = q) on C_{k - 1}, and the following three conditions hold:
     1. For $\ell$ < i < r holds: c_i has no neighbours in G $\setminus$ G_k.
     2. If (c_$\ell$, z₁) $\in$ E, then z₁ immediatelly follows c_{$\ell$ + 1} in the counter-clockwise circular ordering around c_$\ell$ in G.
     3. If (z_p, c_r) $\in$ E, then z_p immediatelly precedes c_{r - 1} in the counter-clockwise circular ordering around c_r in G.

The computation of the canonical ordering (call of the constructor) allows the following options:

• co_type={ co_triconnected, co_biconnected }:
  selects the type of the canonical ordering.
• max_outer={ true, false }:
  determines which face of the graph is used as outerface. Selects the face with maximal degree if max_outer is true, or the first face in the list of faces otherwise.
• prefer_nodes={ false, true }:
  only used for the order type co_triconnected. If in a step of the computation of the ordering, it is possible to select a vertex or a chain as next order set, a vertex is selected if prefer_nodes is true, a chain otherwise.
• base_ratio:
  a double value determining the length of the base, that is the number of nodes in V₁. If base_ratio is r and the outerface is F, the length of the base is min$\left(\vphantom{2,\max\left(\ell, r\Vert F\Vert\right)}\right.$2, max$\left(\vphantom{\ell, r\Vert F\Vert}\right.$$\ell$, r| F| $\left.\vphantom{\ell, r\Vert F\Vert}\right)$ $\left.\vphantom{2,\max\left(\ell, r\Vert F\Vert\right)}\right)$, where $\ell$ = max{k | v₁,..., v_k is a path on F_out with (v_i, v_j)$\notin$E for all j! = i + 1}.

#include < AGD/CanonicalOrder.h >

Creation

CanonicalOrder	C(leda_graph& G, CanonicalOrderType co_type = co_triconnected, leda_face F = nil, bool prefer_nodes = false, double base_ratio = 0.0)
		creates an instance C of type CanonicalOrder initialized to a canonical ordering for triconnected, planar graphs (co_triconnected), or for biconnected, planar graphs (co_biconnected). Precondition: G is a directed graph representing a planar map.

Operations

int	C.length()	returns the number m of sets in the partition.
int	C.len(int i)	returns the length of the i-th set Vi.
leda_node	C(int i, int j)	returns the j-th node of the i-th set Vi.
const OrderSet&	C[int i]	returns a constant reference to the i-th set Vi.
leda_node	C.left(int i)	returns the leftvertex of the i-th set Vi.
leda_node	C.right(int i)	returns the rightvertex of the i-th set Vi.
int	C.rank(leda_node v)	returns the rank of node v, i.e. rank(v) = i$\iff$v $\in$ Vi.

Implementation

The computation of a canonical ordering takes time $\protectO$(n), where n is the number of nodes of G.