For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Minimal Forbidden Minors for the Family of Graphs with Proper-Path-Width at Most Two
Atsushi TAKAHASHI Shuichi UENO Yoji KAJITANI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1995/12/25
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
proper-path-width, path-width, minor-closed family, minimal forbidden minor, VLSI layout,
Full Text: PDF>>
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.