### 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.

Original language | English (US) |
---|---|

Pages (from-to) | 375-390 |

Number of pages | 16 |

Journal | Journal of Algorithms |

Volume | 5 |

Issue number | 3 |

DOIs | |

State | Published - Jan 1 1984 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics

## Fingerprint Dive into the research topics of 'Gauss codes, planar hamiltonian graphs, and stack-sortable permutations'. Together they form a unique fingerprint.

## Cite this

Rosenstiehl, P., & Tarjan, R. E. (1984). Gauss codes, planar hamiltonian graphs, and stack-sortable permutations.

*Journal of Algorithms*,*5*(3), 375-390. https://doi.org/10.1016/0196-6774(84)90018-X