Gauss codes,planar hamiltonian graphs,and stack-sortable permutations |
| |
Authors: | Pierre Rosenstiehl Robert E Tarjan |
| |
Affiliation: | Centre de Mathematique Sociale, Paris, France;AT & T Bell Laboratories, Murray Hill, New Jersey 07974 USA |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|