Electronics circuits keep shrinking in dimensions, as requested by Moore's law. In contrast, photonic waveguides and circuit elements still have lateral dimensions on the order of the wavelength. A key to make photonics have a microelectronics-like development is a drastic reduction of size. To achieve this, we need a low-loss nanoscale waveguide with a drastically reduced mode area and an ultra-high effective refractive index. For this purpose, we propose here several low-loss waveguide structures based on graphene nano-ribbons. An extremely small mode area (~10(-7)λ(0)(2), one order smaller than the smallest mode area of any waveguide that has ever been reported in the literature; here λ(0) is the operating wavelength in vacuum) and an extremely large effective refractive index (several hundreds) are achieved. As a device example, a nano-ring cavity of ultra-small size (with a diameter of ~10(-2)λ(0)) is designed. Our study paves the way for future VLSI (very-large-scale integration) optoelectronics.