A Linear Time Algorithm for Constructing Proper-Path-Decomposition of Width Two

Akira MATSUBAYASHI  Shuichi UENO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E81-A   No.5   pp.729-737
Publication Date: 1998/05/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
proper-path-decomposition,  proper-pathwidth,  pathwidth,  graph layout,  

Full Text: PDF>>
Buy this Article




Summary: 
The problem of constructing the proper-path-decomposition of width at most 2 has an application to the efficient graph layout into ladders. In this paper, we give a linear time algorithm which, for a given graph with maximum vertex degree at most 3, determines whether the proper-pathwidth of the graph is at most 2, and if so, constructs a proper-path-decomposition of width at most 2.