In this paper the following three recognition problems are considered: (1) Test whether a given sequence is the Gauss code of a planar self-intersecting curve; (2) test whether a given graph with a known Hamiltonian cycle is planar; and (3) test whether a given permutation can be sorted using two stacks in parallel. These three problems are closely related: A simple linear-time algorithm that solves all three is described. The heart of the algorithm is a data structure, previously used in general planarity testing, called a pile of twin stacks.
All Science Journal Classification (ASJC) codes
- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics