New graph decompositions and fast emulations in hypercubes and butterflies

Authors:
  • CKChristos Kaklamanis
    Christos Kaklamanis
  • DKDanny Krizanc
    Danny Krizanc
  • SRSatish Rao
    Satish Rao
Open Access
Publisher website
Google Scholar
Abstract
In this paper, we present a new type of graph decomposition called a cut-cover that combines the notions of graph separators and t-neighborhood covers. We show that graphs with good cut-covers can be emulated in hypercubes and butterflies and we show that planar and certain minor-excluded graphs have good cut-covers. In particular, we show how to emulate any N-node bounded degree planar network or any N-node bounded degree graph that excludes KIOgOOl ~ as a minor with constant slowdown on hypercube networks. We also show how to emulate any N-node bounded degree planar network or any IV-node bounded degree graph that excludes Ko(l) as a minor with O(log* N) slowdown on butterfly networks.