Minimal Forbidden Minors for the Family of Graphs with Proper-Path-Width at Most Two

Atsushi TAKAHASHI  Shuichi UENO  Yoji KAJITANI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E78-A   No.12   pp.1828-1839
Publication Date: 1995/12/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
Keyword: 
proper-path-width,  path-width,  minor-closed family,  minimal forbidden minor,  VLSI layout,  

Full Text: PDF>>
Buy this Article




Summary: 
The family Pk of graphs with proper-path-width at most k is minor-closed. It is known that the number of minimal forbidden minors for a minor-closed family of graphs is finite, but we have few such families for which all the minimal forbidden minors are listed. Although the minimal acyclic forbidden minors are characterized for Pk, all the minimal forbidden minors are known only for P1. This paper lists 36 minimal forbidden minors for P2, and shows that there exist no other minimal forbidden minors for P2.