# Noon lecture

On 26.06.2009 at 12:20 in S6, there is the following noon lecture:

# Exact Wirelength of an Embedding

## Abstract

Graph embedding has been known as a powerful strategy for implementation of parallel algorithms or simulation of different interconnection networks. A graph embedding is defined precisely as follows:

Let $G(V,E)$ and $H(V,E)$ be finite graphs with \textit{n} vertices. An embedding $f$ of $G$ into $H$ is defined as follows:

$f$ is a bijective map from $V(G)\rightarrow V(H)$

$f$ is a one-to-one map from $E(G)$ to $\{P_{f}(f(u),f(v)):P_{f}(f(u),f(v))$ is a path in $H$ between $f(u)$ and $f(v)$ for $(u,v)\in E(G)\}.$

The \textit{edge congestion }of an embedding $f$ of $G$ into $H$ is the maximum number of edges of the graph $G$ that are embedded on any single edge of $H$. Let $EC_{f}(G,H(e))$ denote the number of edges $(u,v)$ of $G$ such that $e$ is in the path $P_{f}(f(u),f(v))$ between $f(u)$ and $f(v)$ in $H$. In other words,

\begin{equation*} EC_{f}(G,H(e))=\left\vert

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010