Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations

Reviewer: Douglas M. Campbell

Gauss observed that the points at which a closed oriented curve in the plane intersects itself induce a sequence of integers as follows. A point where the curve crosses itself is a crossing point and a point where the curve touches itself without crossing is a tangent point. If a curve has no tangent points and crosses itself only once at a crossing point, then it is said to be a crossing point curve. If, as we traverse a crossing point curve, we were to number the different crossing points from 1 to n, then we would create a sequence containing each of the symbols 1,2. . ., n exactly twice. Conversely, given a sequence S which contains each of the symbols 1,2. . ., n exactly twice, if we can find a crossing point curve whose associated crossing point sequence is S itself, then S is called a Gauss code. Several characterizations had been developed in terms of forbidden subsequences and an O( n 2) algorithm had been developed by the first author. This lovely paper develops an O( n) algorithm by reducing Gauss codes to two problems of greater familiarity to most computer scientists: testing whether a graph with a known Hamiltonian cycle is planar, and testing whether a permutation is sortable using two stacks in parallel. The proof depends on a new data structure called a pile of twin stacks.