Stack and Queue Layouts of Directed Acyclic Graphs: Part II

DOI10.1137/S0097539795291550zbMath0943.68068OpenAlexW4232763292MaRDI QIDQ4268810

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/s0097539795291550

zbMATH Keywords

posetsbook embeddinggraph algorithmsNP-completegraph embeddingdagsdirected acyclic graphsqueue layoutstack layoutleveled-planar graphs

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 (28)

Queue layouts of iterated line directed graphs ⋮ On the Page Number of Upward Planar Directed Acyclic Graphs ⋮ 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 ⋮ Lazy queue layouts of posets ⋮ Characterization of unlabeled level planar trees ⋮ 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 ⋮ 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 ⋮ Multi-distance granularity structural \(\alpha \)-subtree index of generalized Bethe trees ⋮ Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings ⋮ Recognizing DAGs with page-number 2 is NP-complete ⋮ 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 ⋮ Lazy Queue Layouts of Posets ⋮ Enumeration of BC-subtrees of trees ⋮ On enumerating algorithms of novel multiple leaf-distance granular regular \(\alpha\)-subtrees of trees ⋮ On algorithms for enumerating BC-subtrees of unicyclic and edge-disjoint bicyclic graphs ⋮ On the complexity of recognizing Wheeler graphs

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