Stack and queue layouts of some graph products
Yu Chen · Fuzhou daxue xuebao. Ziran kexue ban · 2009
In this paper,we consider a k - stack (respectively,k - queue) layout of a graph G, which consists of a linear ordering of the vertices,and a partition of the edges into k sets of pairwise non - crossing (respectively,non - nested) edges. The problem of stack layouts (also called book embeddings) and queue layouts abstracts layout problems arising in the routing of multilayer printed circuit boards and in the design of fault - tolerant processor arrays. Motivated by numerous applications to VLSI design and graph drawing,stack layouts and queue layouts are widely studied in the literature,while this paper studies these parameters for direct product,hierarchical product and lexicographic product.