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

DOI10.1016/0196-6774(84)90018-XzbMath0588.68034OpenAlexW2045499731WikidataQ60638468 ScholiaQ60638468MaRDI QIDQ3716310

Pierre Rosenstiehl, Robert Endre 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 algorithmplanarity testingplanar self-intersecting curve

Mathematics Subject Classification ID

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

Related Items

Amortized Computational Complexity, Describing realizable Gauss diagrams using the concepts of parity or bipartite graphs, Permutations sortable by two stacks in parallel and quarter plane walks, Representations of graphs and networks (coding, layouts and embeddings), Permutations generated by stacks and deques, Finding and counting permutations via CSPs, Facilities layout generalized model solved by n-boundary shortest path heuristics, Characterizations of Deque and Queue Graphs