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

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

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

• 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
• 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?)
• 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

(11)

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

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)