Stack and Queue Layouts of Directed Acyclic Graphs: Part I

DOI10.1137/S0097539795280287zbMath0926.68095OpenAlexW1999897678MaRDI QIDQ4268720

Ann N. Trenk, Lenwood S. Heath, Sriram V. Pemmaraju

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539795280287

zbMATH Keywords

book embeddinggraph embeddingdagsdirected acyclic graphsforbidden subgraphqueue layoutstack layout

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99) Applications of graph theory to circuits and networks (94C15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (30)

Queue layouts of iterated line directed graphs ⋮ On the Page Number of Upward Planar Directed Acyclic Graphs ⋮ Upward Point Set Embeddability for Convex Point Sets Is in P ⋮ A Sublinear Bound on the Page Number of Upward Planar Graphs ⋮ Upward book embeddability of \(st\)-graphs: complexity and algorithms ⋮ Recognizing DAGs with page-number 2 is NP-complete ⋮ On upward point set embeddability ⋮ The QC-2 parallel queue processor architecture ⋮ Lazy queue layouts of posets ⋮ Upward Partitioned Book Embeddings ⋮ Graph layouts via layered separators ⋮ Computing Upward Topological Book Embeddings of Upward Planar Digraphs ⋮ Computing upward topological book embeddings of upward planar digraphs ⋮ A new upper bound on the queuenumber of hypercubes ⋮ On Spiro and polyphenyl hexagonal chains with respect to the number of BC-subtrees ⋮ Processor-efficient sparse matrix-vector multiplication ⋮ Upward three-dimensional grid drawings of graphs ⋮ Upper bounds on the queue number of \(k\)-ary \(n\)-cubes ⋮ Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings ⋮ Recognizing DAGs with page-number 2 is NP-complete ⋮ Upward Point-Set Embeddability ⋮ On the Hardness and Inapproximability of Recognizing Wheeler Graphs ⋮ On the upward book thickness problem: combinatorial and complexity results ⋮ Volume requirements of 3D upward drawings ⋮ On the upward book thickness problem: combinatorial and complexity results ⋮ Upward Book Embeddings of st-Graphs ⋮ Characterizations of Deque and Queue Graphs ⋮ Upward straight-line embeddings of directed graphs into point sets ⋮ Lazy Queue Layouts of Posets ⋮ On the complexity of recognizing Wheeler graphs

This page was built for publication: Stack and Queue Layouts of Directed Acyclic Graphs: Part I