Letchford (2000) introduced the domino-parity inequalities for the symmetric traveling salesman problem as a superclass of the comb inequalities proposed by Chvatal (1973) and Grotschel and Padberg (1979). A key result of Letchford is that if the support graph of an LP solution is planar, then the separation problem for domino-parity inequalities can be solved in polynomial time. We generalize domino-parity inequalities to multi-handled configurations, introducing a superclass of bipartition and star inequalities. Also, we generalize Letchford's algorithm, proving that for a fixed integer k, one can separate a superclass of k-handled clique-tree inequalities satisfying certain connectivity characteristics with respect to the planar support graph. We describe an implementation of this algorithm which is exact for a single handle (that is, Letchford's Algorithm) and a heuristic for the case of two handles. This implementation includes pruning methods to restrict the search for dominoes, a parallelization of the main domino-building step, heuristics to obtain planar-support graphs, a safe-shrinking routine, a random-walk heuristic to extract additional violated constraints, and a tightening procedure to allow us to modify existing inequalities as the LP solution changes. We report computational results showing the strength of the new routines, including the optimal solution of the TSPLIB instance pla33810.