Algorithms for min-cut linear arrangements of outerplanar graphs
Liang-Fang Chao, Edwin H.‐M. Sha · 2003
A linear arrangement (LA) is an embedding of an outerplanar graph G in a row of nodes. A linear-time approximation algorithm is presented to find an LA with cutwidth optimal within a constant factor. The Planar LA is an LA such that no two edges cross each other. Algorithms for this problem are also discussed. An abstraction, called a dual tree, is used to design these algorithms.>