Mutual Embeddings

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.