I need to find the deexcitation times for the transitions found in Figure 1 of Nature Phys. 8, 649 (2012), arXiv:1206.4507.
That is, what is the deexcitation time for the following transitions:
$$ ^2P_{1/2} \rightarrow {}^2S_{1/2} $$ $$ ^2P_{1/2} \rightarrow {}^2D_{3/2} $$ $$ ^2D_{3/2} \rightarrow {}^2S_{1/2} $$ $$ ^2D_{5/2} \rightarrow {}^2F_{7/2} $$
I've searched on google for pretty much everything I can think of , but I was not able to find a data table with these deexcitation times.
Most of what's making life difficult is that you're using the wrong terminology. The term "deexcitation" can be understood by a human but it is not standard or recommended, and it definitely won't be understood by a machine. What you're looking for are more normally called the state and transition lifetimes and probabilities.
The place to look is the NIST Atomic Spectra Databases, particularly the one for atomic lines. I can't link to the Ytterbium page (it's a dynamic page), but the $A_{ki}$ are the data you want - they are the transition probabilities, in $\mathrm s^{-1}$, for the transition. Invert those to get the lifetimes. If the information you want is not on there, there is a wealth of bibliographic information lying about the site which can probably help you find what you need.
For the specific transitions listed in the diagram, the NIST database only lists two, ${}^2 P_{1/2}\to{}^2 S_{1/2}$ and ${}^3 [3/2]_{3/2}\to{}^2 S_{1/2}$ (which you took down as ${}^2D_{3/2}\to{}^2 S_{1/2}$, but that is incorrect) for the Yb II spectra (note that this is the ytterbium ion, not the neutral): \begin{align} \text{Transition} & & \text{Wavelength} & & A_{ki} & & A_{ki}^{-1}\\\hline {}^2 P_{1/2}\to{}^2 S_{1/2} & & 369\:\mathrm{nm} & & 123\:\mathrm{\mu s}^{-1} & & 8.13 \:\mathrm{ns} \\ {}^3 [3/2]_{1/2}\to{}^2 S_{1/2} & & 297\:\mathrm{nm} & & 26.1\:\mathrm{\mu s}^{-1} & & 38\:\mathrm{ns} \end{align}
If you want to go beyond this you can click on the reference on the far-right corner, which then lets you find all the bibliography on the species in question. Using this you can find, for example, Phys. Rev. A 60, 2829 (1999), which gives
\begin{align} \ \ \ \ \ \ {}^2 D_{5/2}\to{}^2 F_{7/2} & &\ \ \ \ \ \ \ 3.43\:\mathrm{\mu m} & & 0.905\:\mathrm{\mu s}^{-1} & & 1.10\:\mathrm{\mu s} \end{align}
Note that this is out of the wavelength range in the NIST database.
You can get the wavelength of the final transition, ${}^2 P_{1/2}\to{}^2 D_{3/2}$, using energy level data from Atomic Energy Levels - The Rare-Earth Elements by Martin, Zalubas and Hagan, and it comes out as $2.4\:\mathrm{\mu m}$, also outside of the range in the NIST database. If you're happy with a theoretical calculation then J. Phys. B: At. Mol. Opt. Phys. 45 145002 (2012) gives estimates from $A_{ki}= 47\:\mathrm{ms}^{-1}$ to $2.98\:\mathrm{\mu s}^{-1}$, which is not very comforting, but the real issue with this transition is that it is very hard to measure.
In particular, if you put an ytterbium ion in the ${}^2P_{1/2}$ state, what it will do almost immediately is decay via the dipole transition to the ground state, ${}^2S_{1/2}$, with very little of the population ending up in the metastable ${}^2D_{3/2}$ state. What you care about, then, is the branching ratio in the decay of the ${}^2P_{1/2}$ state, which is measured at $0.0005$ by Phys. Rev. A 76, 052314 (2007), from an overall lifetime of $8.07\:\mathrm{ns}$.