DocumentCode
285670
Title
Algorithms for min-cut linear arrangements of outerplanar graphs
Author
Chao, Liang-Fang ; Sha, Edwin Hsing-Mean
Author_Institution
Dept. of Comput. Sci., Princeton Univ., NJ, USA
Volume
4
fYear
1992
fDate
3-6 May 1992
Firstpage
1851
Abstract
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
Keywords
graph theory; algorithm design; cutwidth optimal; dual tree; linear-time approximation algorithm; min-cut linear arrangements; no two edges cross; outerplanar graph embedding; outerplanar graphs; planar linear arrangement; Approximation algorithms; Books; Chaos; Density measurement; Design automation; Embedded computing; Linear approximation; Measurement standards; Tree graphs; Very large scale integration;
fLanguage
English
Publisher
ieee
Conference_Titel
Circuits and Systems, 1992. ISCAS '92. Proceedings., 1992 IEEE International Symposium on
Conference_Location
San Diego, CA
Print_ISBN
0-7803-0593-0
Type
conf
DOI
10.1109/ISCAS.1992.230392
Filename
230392
Link To Document