Pathwidth of planar and line graphs

被引：1

作者：

Fomin, FV ^{[1
]}

机构：

[1] Univ Paderborn, Heinz Nixdorf Inst, D-33102 Paderborn, Germany

来源：

GRAPHS AND COMBINATORICS | 2003年 / 19卷 / 01期

关键词：

pathwidth; treewidth; planar graphs; line graphs;

D O I：

10.1007/s00373-002-0490-z

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that for every 2-connected planar graph the pathwidth of its geometric dual is less than the pathwidth of its line graph. This implies that pathwidth(H) less than or equal to pathwidth(H*) + 1 for every planar triangulation H and leads us to a conjecture that pathwidth(G) less than or equal to pathwidth(G*) + 1 for every 2-connected graph G.

引用

页码：91 / 99

页数：9

共 21 条

[1] MONOTONICITY IN GRAPH SEARCHING
BIENSTOCK, D
SEYMOUR, P
[J]. JOURNAL OF ALGORITHMS, 1991, 12 (02) : 239 - 245
[2] Bienstock D, 1991, DIMACS SER DISCRETE, V5, P33, DOI DOI 10.1090/DIMACS/005/02
[3] A partial k-arboretum of graphs with bounded treewidth
Bodlaender, HL
[J]. THEORETICAL COMPUTER SCIENCE, 1998, 209 (1-2) : 1 - 45
[4] BONDUELLE M, 1995, HUM REPROD UPDATE, V1, P3
[5] BOUCHITTE V, 2001, UNPUB TREEWIDTH PLAN
[6] Fugitive-search games on graphs and related parameters
Dendris, ND
Kirousis, LM
Thilikos, DM
[J]. THEORETICAL COMPUTER SCIENCE, 1997, 172 (1-2) : 233 - 254
[7] Diestel R., 1997, Graph Theory
[8] THE VERTEX SEPARATION AND SEARCH NUMBER OF A GRAPH
ELLIS, JA
SUDBOROUGH, IH
TURNER, JS
[J]. INFORMATION AND COMPUTATION, 1994, 113 (01) : 50 - 79
[9] Golovach P. A., 1993, DISCRETE MATH APPL, V3, P517, DOI DOI 10.1515/DMA.1993.3.5.517
[10] THE VERTEX SEPARATION NUMBER OF A GRAPH EQUALS ITS PATH-WIDTH
KINNERSLEY, NG
[J]. INFORMATION PROCESSING LETTERS, 1992, 42 (06) : 345 - 350

← 1 2 3 →