Stack and queue number of 2-trees

被引：0

作者：

Rengarajan, S

Madhavan, CEV

机构：

来源：

COMPUTING AND COMBINATORICS | 1995年 / 959卷

关键词：

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the two problems of embedding graphs in a minimum number of pages and ordering the vertices of graphs in the form of queue layouts. We show that the class of 2-trees requires 2-pages for a book embedding and 3-queues for a queue layout. The first result is new and the latter result extends known results on subclasses of planar graphs.

引用

页码：203 / 212

页数：10

共 8 条

[1] BOOK THICKNESS OF A GRAPH
BERNHART, F
KAINEN, PC
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1979, 27 (03) : 320 - 331
[2] EMBEDDING GRAPHS IN BOOKS - A LAYOUT PROBLEM WITH APPLICATIONS TO VLSI DESIGN
CHUNG, FRK
LEIGHTON, FT
ROSENBERG, AL
[J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (01): : 33 - 58
[3] LAYING OUT GRAPHS USING QUEUES
HEATH, LS
ROSENBERG, AL
[J]. SIAM JOURNAL ON COMPUTING, 1992, 21 (05) : 927 - 958
[4] GENUS-G GRAPHS HAVE PAGENUMBER O(ROOT-G)
MALITZ, SM
[J]. JOURNAL OF ALGORITHMS, 1994, 17 (01) : 85 - 109
[5] GRAPHS WITH E-EDGES HAVE PAGENUMBER O(ROOT-E)
MALITZ, SM
[J]. JOURNAL OF ALGORITHMS, 1994, 17 (01) : 71 - 84
[6] 2-PAGE BOOK EMBEDDING OF TREES UNDER VERTEX-NEIGHBORHOOD CONSTRAINTS
MORAN, S
WOLFSTHAL, Y
[J]. DISCRETE APPLIED MATHEMATICS, 1993, 43 (03) : 233 - 241
[7] OBRENIC B, 1991, 3RD P ANN ACM S PAR, P137
[8] ROSENBERG AL, 1983, IEEE T COMPUT, V32, P902, DOI 10.1109/TC.1983.1676134

← 1 →