Show simple item record

dc.contributor.authorHeath, Lenwood S.en_US
dc.date.accessioned2013-06-19T14:36:59Z
dc.date.available2013-06-19T14:36:59Z
dc.date.issued1993
dc.identifierhttp://eprints.cs.vt.edu/archive/00000382/en_US
dc.identifier.urihttp://hdl.handle.net/10919/19774
dc.description.abstractAn undirected graph is viewed as a simplicial complex. The notion of a graph embedding of a guest graph in a host graph is generalized to the realm of simplicial maps. Dilation is redefined in this more general setting. Lower bounds on dilation for various guest and host graphs are considered. Of particular interest are graphs that have been proposed as communication networks for parallel architectures. Bhatt et al. provide a lower bound on dilation for embedding a planar guest graph in a butterfly host graph. Here, this lower bound is extended in two directions. First, a lower bound that applies to arbitrary guest graphs is derived, using tools from algebraic topology. Second, this lower bound is shown to apply to arbitrary host graphs through a new graph-theoretic measure, called bidecomposability. Bounds on the bidecomposability of the butterfly graph and of the k-dimensional torus are determined. As corollaries to the main lower bound theorem, lower bounds are derived for embedding arbitrary planar graphs, genus g graphs, and k-dimensional meshes in a butterfly host graph.en_US
dc.format.mimetypeapplication/pdfen_US
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen_US
dc.relation.ispartofHistorical Collection(Till Dec 2001)en_US
dc.titleGraph Embeddings and Simplicial Mapsen_US
dc.typeTechnical reporten_US
dc.identifier.trnumberTR-93-40en_US
dc.type.dcmitypeTexten_US
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000382/01/TR-93-40.pdf


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record