GrafEq [1] from Pedagoguery Software is one of best-known softwares that can handle a variety of implicit 2D plots (it's a shareware, though). The algorithm for its earlier version is based on generalized interval arithmetics and described in the author's thesis [2]. I like it so much that reimplementing it is one of my (ever-growing) longer-term projects...

[1] http://www.peda.com/grafeq/

[2] http://www.dgp.toronto.edu/~mooncake/thesis.pdf