  We study generalizations of classical metric embedding results to the case of
quasimetric spaces; that is, spaces that do not necessarily satisfy symmetry.
Quasimetric spaces arise naturally from the shortest-path distances on directed
graphs. Perhaps surprisingly, very little is known about low-distortion
embeddings for quasimetric spaces.
  Random embeddings into ultrametric spaces are arguably one of the most
successful geometric tools in the context of algorithm design. We extend this
to the quasimetric case as follows. We show that any $n$-point quasimetric
space supported on a graph of treewidth $t$ admits a random embedding into
quasiultrametric spaces with distortion $O(t \log^2 n)$, where
quasiultrametrics are a natural generalization of ultrametrics. This result
allows us to obtain $t\log^{O(1)} n$-approximation algorithms for the Directed
Non-Bipartite Sparsest-Cut and the Directed Multicut problems on $n$-vertex
graphs of treewidth $t$, with running time polynomial in both $n$ and $t$.
  The above results are obtained by considering a generalization of random
partitions to the quasimetric case, which we refer to as random
quasipartitions. Using this definition and a construction of [Chuzhoy and
Khanna 2009] we derive a polynomial lower bound on the distortion of random
embeddings of general quasimetric spaces into quasiultrametric spaces. Finally,
we establish a lower bound for embedding the shortest-path quasimetric of a
graph $G$ into graphs that exclude $G$ as a minor. This lower bound is used to
show that several embedding results from the metric case do not have natural
analogues in the quasimetric setting.
