ON THE CODING OF ORDERED GRAPHS

Ordered graph and ordered graph isomorphism provide a natural represen tation of many objects in applications such as computational geometry, computer vision and pattern recognition. In the present paper we prop ose a coding procedure for ordered graphs that improves an earlier one based on Eulerian circuits of graphs in terms of both simplicity and computational efficiency. Using our coding approach, we show that the ordered graph isomorphism problem can be optimally solved in quadratic time, although no efficient (polynomial-bound) isomorphism algorithm for general graphs exists today. An experimental evaluation demonstrat es the superior performance of the new method.