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

Pierre Rosenstiehl, Robert Endre Tarjan

Research output: Contribution to journalArticle

22 Scopus citations

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 languageEnglish (US)
Pages (from-to)375-390
Number of pages16
JournalJournal of Algorithms
Volume5
Issue number3
DOIs
StatePublished - Jan 1 1984
Externally publishedYes

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