Mutual Embeddings


Journal Article

© 2015 World Scientific Publishing Company. This paper introduces a type of graph embedding called a mutual embedding. A mutual embedding between two n-node graphs G1=(V1, E1) and G2=(V2,E2) is an identification of the vertices of V1 and V2, i.e., a bijection :V1aV 2, together with an embedding of G1 into G2 and an embedding of G2 into G1 where in the embedding of G1 into G2, each node u of G1 is mapped to (u) in G2 and in the embedding of G2 into G1 each node v of G2 is mapped to-1(v) in G1. The identification of vertices in G1 and G2 constrains the two embeddings so that it is not always possible for both to exhibit small congestion and dilation, even if there are traditional one-way embeddings in both directions with small congestion and dilation. Mutual embeddings arise in the context of finding preconditioners for accelerating the convergence of iterative methods for solving systems of linear equations. We present mutual embeddings between several types of graphs such as linear arrays, cycles, trees, and meshes, prove lower bounds on mutual embeddings between several classes of graphs, and present some open problems related to optimal mutual embeddings.

Full Text

Duke Authors

Cited Authors

  • Bozkurt, IN; Huang, H; Maggs, B; Richa, A; Woo, M

Published Date

  • October 1, 2015

Published In

Volume / Issue

  • 15 / 1-2

Electronic International Standard Serial Number (EISSN)

  • 1793-6713

International Standard Serial Number (ISSN)

  • 0219-2659

Digital Object Identifier (DOI)

  • 10.1142/S0219265915500012

Citation Source

  • Scopus