Hyperpolarized (HP) propane is a promising contrast agent for magnetic resonance imaging (MRI) of lungs and for studying porous media. The parahydrogen-induced polarization (PHIP) technique is a convenient approach to produce pure propane gas with enhanced proton polarization, when hydrogenation of propylene with parahydrogen is performed over heterogeneous catalysts. Here, we present a new approach of multidimensional mapping of the efficiency of pairwise parahydrogen addition using PHIP-echo pulse sequence. We use this approach to study the performance of three model heterogeneous Rh/TiO2 catalysts in the production of HP propane gas. The three catalysts with 1.0, 13.7, and 23.2 wt % of supported rhodium nanoparticles have been characterized by X-ray photoelectron spectroscopy (XPS) and high resolution transition electron microscopy (HRTEM). By varying the fractions of parahydrogen and propylene in the reactant mixture as well as the gas mixture pressure, 2D maps of PHIP-echo NMR signal and 2D maps of HP propane NMR signal enhancement were obtained. These maps clearly indicate that lower metal coverage results in more efficient pairwise hydrogen addition, producing greater levels of proton polarization of propane gas. The presented method can be extended to multidimensional characterization of the influence of other key parameters of PHIP reaction process including temperature or addition of an inert carrier gas. A 2D T1 relaxation map of propane at 9.4 T is also reported as a function of propane fraction (in the mixture with hydrogen) and gas mixture pressure.