Characterizations of deque and queue graphs

DOI10.1007/978-3-642-25870-1_5MaRDI QIDQ3104763zbMATH OpenOpenAlexFDO

Authors Christopher Auer, Andreas Gleißner

Publication date 16 December 2011

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-25870-1_5

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Data Structures and their Planar Graph Layouts
• Plane Drawings of Queue and Deque Graphs
• Laying Out Graphs Using Queues
• Stack and Queue Layouts of Directed Acyclic Graphs: Part II
• Characterizing planarity by the splittable deque

Cites work

• scientific article; zbMATH DE number 2084286 (Why is no real title available?)
• scientific article; zbMATH DE number 4049084 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1954397 (Why is no real title available?)
• scientific article; zbMATH DE number 2159644 (Why is no real title available?)
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Embedding planar graphs in four pages
• Gauss codes, planar hamiltonian graphs, and stack-sortable permutations
• Hierarchies and planarity theory
• Laying Out Graphs Using Queues
• Plane Drawings of Queue and Deque Graphs
• Stack and Queue Layouts of Directed Acyclic Graphs: Part I
• Stack and Queue Layouts of Directed Acyclic Graphs: Part II
• Stacks, queues and tracks: layouts of graph subdivisions
• The book thickness of a graph

Cited in

(10)

• Finding geometric representations of apex graphs is NP-hard
• Deque languages, automata and planar graphs
• Linear layouts of bipartite planar graphs
• Data Structures and their Planar Graph Layouts
• Plane Drawings of Queue and Deque Graphs
• Recognizing geometric intersection graphs stabbed by a line
• Characterizing planarity by the splittable deque
• Finding geometric representations of apex graphs is \textsf{NP}-hard
• Deque automata, languages, and planar graph representations
• Upward planar drawings on the standing and the rolling cylinders

This page was built for publication: Characterizations of deque and queue graphs

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