We present a linear time algorithm for computing linear layouts of trees which are optimal with respect to vertex separation. The best algorithm known so far is given by Ellis, Sudborough, and Turner, and needs O(n log n) time. Our result solves several other related open problems on trees as for example the one of Papadimitriou, Garey, Johnson, Megiddo, and Hakimi.
Erika Cetindag, Martin Griebl