A novel approach to stability analysis of linear time-invariant (LTI) time-delay systems of retarded type with incommensurate time delays and polynomial dependence on parametric uncertainties is presented. Using a branch and bound algorithm, which relies on Taylor models and polynomials in Bernstein form, we first determine the stability-crossing set in the delay/parameter space and then evaluate stability for each disjoint region. The novel approach can be used to either non-conservatively check stability of time-delay systems with interval parameters or to map stable regions to a low-dimensional parameter space while taking additional interval parameters into account. The algorithm is applied to several examples with parametric uncertainties and/or incommensurate time delays.