Mutual Embeddings

Ilker Nadi Bozkurt, Hai Huang, Bruce Maggs, Andrea Richa, Maverick Woo

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number1550001
JournalJournal of Interconnection Networks
Issue number1-2
StatePublished - Oct 1 2015


  • Graph embedding
  • mutual embedding
  • support tree preconditioners

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'Mutual Embeddings'. Together they form a unique fingerprint.

Cite this