This paper proposes a novel graphical method to compute all feasible gain and phase margin specifications-oriented robust PID controllers to stabilize uncertain control systems with time-varying delay. A virtual gain-phase margin tester compensator is incorporated to guarantee the concerned system with certain robust safety margins. The complex Kharitonov theorem is used to characterize the parametric uncertainties of the considered system and is exploited as a stability criterion for the Hurwitz property of a family of polynomials with complex coefficients varying within given intervals. The coefficients of the characteristic equation are overbounded and eight vertex Kharitonov polynomials are derived to perform stability analysis. The stability equation method and the parameter plane method are exploited to portray constant gain margin and phase margin boundaries. The feasible controllers stabilizing every one of the eight vertex polynomials are identified in the parameter plane by taking the overlapped region of the plotted boundaries. The overlapped region of the useful region of each vertex polynomial is the Kharitonov region, which represents all the feasible specifications-oriented robust PID controller gain sets. Variations of the Kharitonov region with respect to variations of the derivative gain are extensively studied. The way to select representative points from the Kharitonov region for designing robust controllers is suggested. Finally, three illustrative examples with computer simulations are provided to demonstrate the effectiveness and confirm the validity of the proposed methodology. Based on the pre-specified gain and phase margin specifications, a non-conservative Kharitonov region can be graphically identified directly in the parameter plane for designing robust PID controllers. (C) 2011 Elsevier Ltd. All rights reserved.