A finite-difference time-domain (FD-TD) algorithm is described for the efficient full-wave analysis of a comprehensive class of millimeter-wave and optical waveguide structures. The FD-TD algorithm is based on a two-dimensional graded mesh combined with adequately formulated absorbing boundary conditions. This allows the inclusion of nearly arbitrarily shaped, fully or partially lateral open or shielded guiding structures with or without layers of finite metallization thickness. Moreover, lossy dielectrics and/or lossy conductors are included in the theory. The algorithm leads to a significant reduction in cpu time and storage requirements as compared with the conventional three-dimensional eigenvalue FD-TD mesh formulation. Dispersion characteristic examples are calculated for structures suitable for usual integrated circuits, such as insulated image guides, ridge guides, dielectric waveguides, trapped image guides, coplanar-lines and microstrip lines. The theory is verified by comparison with results obtained by other methods.