This algorithm is likely very slow. In fact, the authors didn't mention runtime at all.

Yes, there are other high performance candidates that work well with line art. http://en.wikipedia.org/wiki/Hq3x

Depixelizing Pixel Art may work even better for some types of images: http://research.microsoft.com/en-us/um/people/kopf/pixelart/ "The algorithm extracts a smooth, resolution-independent vector representation from the image, which enables magnifying the results by an arbitrary amount without image degradation."

I tried HQX and the results are impressive! I have abandonned the Python tool because the installation is tedious but this one is very straightforward.

It doesn't have to be slow - it may be possible to write a shader that does it on a GPU.

Yup! If it was fast enough this could really help to bridge the retina resolution lag.