Stack and Queue Layouts of Directed Acyclic Graphs: Part II

DOI10.1137/S0097539795291550MaRDI QIDQ4268810zbMATH OpenOpenAlexFDO

Authors Lenwood S. Heath, Sriram 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

graph algorithmsgraph embeddingNP-completeposetsdirected acyclic graphsbook embeddingqueue layoutdagsstack layoutleveled-planar graphs

Mathematics Subject Classification ID

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

Recommendations

• Stack and Queue Layouts of Directed Acyclic Graphs: Part I
• scientific article; zbMATH DE number 431507
• Laying Out Graphs Using Queues
• Comparing Queues and Stacks As Machines for Laying Out Graphs

Cited in

(38)

• Computing Upward Topological Book Embeddings of Upward Planar Digraphs
• Linear layout of directed grid graph
• On the page number of upward planar directed acyclic graphs
• On algorithms for enumerating BC-subtrees of unicyclic and edge-disjoint bicyclic graphs
• On enumerating algorithms of novel multiple leaf-distance granular regular \(\alpha\)-subtrees of trees
• Multi-distance granularity structural \(\alpha \)-subtree index of generalized Bethe trees
• On families of planar DAGs with constant stack number
• Stack and Queue Layouts of Directed Acyclic Graphs: Part I
• Stack and queue number of 2-trees
• Lazy queue layouts of posets
• Characterizations of deque and queue graphs
• On the upward book thickness problem: combinatorial and complexity results
• On the complexity of recognizing Wheeler graphs
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Computing upward topological book embeddings of upward planar digraphs
• A Sublinear Bound on the Page Number of Upward Planar Graphs
• Volume requirements of 3D upward drawings
• Processor-efficient sparse matrix-vector multiplication
• Upward book embeddings of st-graphs
• Queue layouts of iterated line directed graphs
• Upward book embeddability of \(st\)-graphs: complexity and algorithms
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Enumeration of BC-subtrees of trees
• Characterization of unlabeled level planar trees
• Upward three-dimensional grid drawings of graphs
• Graph layouts via layered separators
• Directed acyclic outerplanar graphs have constant stack number
• Upward partitioned book embeddings
• Lazy Queue Layouts of Posets
• Recognizing DAGs with page-number 2 is NP-complete
• Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings
• Stack and queue layouts of some graph products
• Recognizing DAGs with page-number 2 is NP-complete
• scientific article; zbMATH DE number 431507 (Why is no real title available?)
• On spiro and polyphenyl hexagonal chains with respect to the number of BC-subtrees
• On the upward book thickness problem: combinatorial and complexity results
• Queue layouts of two-dimensional posets
• On 1-bend upward point-set embeddings of \(st\)-digraphs

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

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