We present a new method that uses the pulse oximeter signal to estimate the respiratory rate. The method uses a recently developed time-frequency spectral estimation method, variable-frequency complex demodulation (VFCDM), to identify frequency modulation (FM) of the photoplethysmogram waveform. This FM has a measurable periodicity, which provides an estimate of the respiration period. We compared the performance of VFCDM to the continuous wavelet transform (CWT) and autoregressive (AR) model approaches. The CWT method also utilizes the respiratory sinus arrhythmia effect as represented by either FM or AM to estimate respiratory rates. Both CWT and AR model methods have been previously shown to provide reasonably good estimates of breathing rates that are in the normal range (12-26 breaths/min). However, to our knowledge, breathing rates higher than 26 breaths/min and the real-time performance of these algorithms are yet to be tested. Our analysis based on 15 healthy subjects reveals that the VFCDM method provides the best results in terms of accuracy (smaller median error), consistency (smaller interquartile range of the median value), and computational efficiency (less than 0.3 s on 1 min of data using a MATLAB implementation) to extract breathing rates that varied from 12-36 breaths/min.