On the coding of ordered graphs (Q1266307)

This paper describes a coding procedure for ordered graphs. Using this procedure it is shown that the ordered graph isomorphism problem can be optimally solved in quadratic time. If \(X\) is a set of graphs and \(Y\) the set of strings of symbols from some alphabet, then a coding procedure is a mapping \(c:X\to Y\) such that two graphs in \(X\) map into the same string of \(Y\) if and only if they are isomorphic. An ordered graph is an undirected graph \(G=(V,E)\) where for each vertex \(v\in V\) there is a cyclic ordering \(L(v)\) of the neighbors of \(v\). Two ordered graphs are ordered isomorphic if there exists a bijection between their vertex sets that preserves both adjacency and order. This paper describes a coding procedure for ordered graphs. Given an ordered graph with \(m\) edges, the procedure produces a total of \(2m\) subcodes (two per edge) where each subcode is a string of \(2m\) natural numbers. The lexicographically least of these is then chosen as the code for the graph. It is shown that two graphs are ordered isomorphic if and only if they have the same code. An \(O(m^2)\) algorithm to determine whether two ordered graphs are ordered isomorphic is given. The authors provide experimental evidence which underlines the efficiency of their approach.