乘积图的堆栈布局和队列布局  

Stack and queue layouts of some graph products

作　　者：陈育栎[1] 

机构地区：[1]福州大学至诚学院,福建福州350002

出　　处：《福州大学学报（自然科学版）》2009年第6期793-797,共5页Journal of Fuzhou University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(10971027)

摘　　要：考虑图布局问题的k-栈布局以及k-队列布局问题,即将图中所有点进行线性排序后,其边集可以划分成k个内部边相互不交叉或者k个边集内部不相互嵌套的集合.图的堆栈布局问题(也称为图的书式嵌入问题)以及队列布局问题来源于多层电路板的布线以及容错处理器阵列的设计,它广泛应用于超大规模集成电路的设计以及图的绘制等各个方面.在关于图的堆栈布局以及队列布局问题的广泛研究基础上,专注于若干种乘积图布局中的堆栈布局和队列布局.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 lexieographic product.

关 键 词：图 布局 堆栈 队列 乘积 

分 类 号：O157.5[理学—数学]