Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs

被引：6
作者：
Togasaki, M [1 ]
Yamazaki, K [1 ]
机构：
[1] Gunma Univ, Dept Comp Sci, Kiryu, Gumma 3768515, Japan
来源：
DISCRETE MATHEMATICS | 2002年 / 259卷 / 1-3期
关键词：
pagenumber; book embedding; pathwidth; strong pathwidth;
D O I：
10.1016/S0012-365X(02)00542-3
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
In this paper, it is shown that the maximum pagenumber of the graphs with pathwidth k is k and that the maximum pagenumber of the graphs with strong pathwidth k is in between [3(k - 1)/2] and 3 [k/2]. (C) 2002 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：361 / 368
页数：8
相关论文
共 12 条
  • [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 SURVEY
    BILSKI, T
    [J]. IEE PROCEEDINGS-E COMPUTERS AND DIGITAL TECHNIQUES, 1992, 139 (02): : 134 - 138
  • [3] A partial k-arboretum of graphs with bounded treewidth
    Bodlaender, HL
    [J]. THEORETICAL COMPUTER SCIENCE, 1998, 209 (1-2) : 1 - 45
  • [4] A linear-time ie algorithm for finding three-decompositions of small treewidth
    Bodlaender, HL
    [J]. SIAM JOURNAL ON COMPUTING, 1996, 25 (06) : 1305 - 1317
  • [5] 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
  • [6] On the pagenumber of complete bipartite graphs
    Enomoto, H
    Nakamigawa, T
    Ota, K
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1997, 71 (01) : 111 - 120
  • [7] The pagenumber of k-trees is O(k)
    Ganley, Joseph L.
    Heath, Lenwood S.
    [J]. 1600, Elsevier (109):
  • [8] THE COMPLEXITY OF COLORING CIRCULAR ARCS AND CHORDS
    GAREY, MR
    JOHNSON, DS
    MILLER, GL
    PAPADIMITRIOU, CH
    [J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1980, 1 (02): : 216 - 227
  • [9] HASUNUMA T, 1999, AUSTRAL COMPUT SCI C, V21, P232
  • [10] PAGENUMBER OF COMPLETE BIPARTITE GRAPHS
    MUDER, DJ
    WEAVER, ML
    WEST, DB
    [J]. JOURNAL OF GRAPH THEORY, 1988, 12 (04) : 469 - 489
12