  The paper is divided in to two parts. In the first part we present some new
results for the \textit{routing via matching} model introduced by Alon et
al\cite{5}. This model can be viewed as a communication scheme on a distributed
network. The nodes in the network can communicate via matchings (a step), where
a node exchanges data with its partner. Formally, given a connected graph $G$
with vertices labeled from $[1,...,n]$ and a permutation $\pi$ giving the
destination of pebbles on the vertices the problem is to find a minimum step
routing scheme. This is denoted as the routing time $rt(G,\pi)$ of $G$ given
$\pi$. In this paper we present the following new results, which answer one of
the open problems posed in \cite{5}: 1) Determining whether $rt(G,\pi)$ is $\le
2$ can be done in $O(n^{2.5})$ deterministic time for any arbitrary connected
graph $G$. 2) Determining whether $rt(G,\pi)$ is $\le k$ for any $k \ge 3$ is
NP-Complete. In the second part we study a related property of graphs, which
measures how easy it is to design sorting networks using only the edges of a
given graph. Informally, \textit{sorting number} of a graph is the minimum
depth sorting network that only uses edges of the graph. Many of the classical
results on sorting networks can be represented in this framework. We show that
a tree with maximum degree $\Delta$ can accommodate a $O(\min(n\Delta^2,n^2))$
depth sorting network. Additionally, we give two instance of trees for which
this bound is tight.
