Premium
Divide‐and‐conquer algorithms for graph‐layout problems
Author(s) -
Swaminathan Ram
Publication year - 1996
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199609)28:2<69::aid-net1>3.0.co;2-a
Subject(s) - computer science , algorithm , modular decomposition , divide and conquer algorithms , embedding , pathwidth , time complexity , theoretical computer science , graph , mathematics , line graph , artificial intelligence
Tutte introduced a decomposition of 2‐connected graphs which has widely been used in solving various graph‐theoretic problems. In this paper, we extend it to a class of graph‐layout problems, namely, determining the bandwidth, cutwidth, and pagenumber of graphs. In particular, we present linear‐time algorithms for testing and, if so, constructing linear layouts of 2‐edge‐connected bandwidth‐2 and cut‐width‐3 graphs. We also present a simple linear‐time algorithm for embedding series‐parallel graphs in two pages. The interesting feature of these algorithms is that they use a divide‐and‐conquer paradigm with Tutte decomposition of 2‐connected graphs as a common framework; thus, they are different from the previously known algorithms. Moreover, since Tutte decomposition can be computed efficiently in parallel, all three proposed algorithms parallelize naturally. © 1996 John Wiley & Sons, Inc.