The linear arrangement problem on recursively constructed graphs
The linear arrangement problem on graphs is a relatively old and quite well-known problem. Hard in general, it remains open on general recursive graphs (i.e., partial k-trees, etc.), which is somewhat frustrating since most hard graph problems are easily solved on recursive graphs. In this paper, we examine the linear arrangement problem with respect to these structures. Included are some negative (complexity) results as well as a solvable case. (C) 2003 Wiley Periodicals, Inc.
complexity optimal linear arrangement halin graphs