  Embeddings of graphs into distributions of trees that preserve distances in
expectation are a cornerstone of many optimization algorithms. Unfortunately,
online or dynamic algorithms which use these embeddings seem inherently
randomized and ill-suited against adaptive adversaries.
  In this paper we provide a new tree embedding which addresses these issues by
deterministically embedding a graph into a single tree containing $O(\log n)$
copies of each vertex while preserving the connectivity structure of every
subgraph and $O(\log^2 n)$-approximating the cost of every subgraph.
  Using this embedding we obtain several new algorithmic results: We reduce an
open question of Alon et al. [SODA 2004] -- the existence of a deterministic
poly-log-competitive algorithm for online group Steiner tree on a general graph
-- to its tree case. We give a poly-log-competitive deterministic algorithm for
a closely related problem -- online partial group Steiner tree -- which,
roughly, is a bicriteria version of online group Steiner tree. Lastly, we give
the first poly-log approximations for demand-robust Steiner forest, group
Steiner tree and group Steiner forest.
