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

DOI10.1016/0196-6774(84)90018-XMaRDI QIDQ3716310zbMATH OpenOpenAlexWikidataFDO

Authors Pierre Rosenstiehl, Robert E. Tarjan

Publication date 1984

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(84)90018-x

zbMATH Keywords

linear-time algorithmplanar self-intersecting curveplanarity testing

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The Gauss code problem off the plane
• On a characterization of Gauss codes
• A survey of stack-sorting disciplines
• 2-stack sorting is polynomial
• 2-stack sorting is polynomial

Cited in

(11)

• Representations of graphs and networks (coding, layouts and embeddings)
• Facilities layout generalized model solved by n-boundary shortest path heuristics
• Finding and counting permutations via CSPs
• Characterizations of deque and queue graphs
• Amortized Computational Complexity
• Permutations sortable by two stacks in parallel and quarter plane walks
• Describing realizable Gauss diagrams using the concepts of parity or bipartite graphs
• Han's bijection via permutation codes
• Meanders: a personal perspective to the memory of Pierre Rosenstiehl
• Permutations generated by stacks and deques
• Classification of small links in the unmarked solid torus

This page was built for publication: Gauss codes, planar hamiltonian graphs, and stack-sortable permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3716310)