Letchford (2000) introduced the domino-parity inequalities for the symmetric traveling salesman problem and showed that if the support graph of an LP solution is planar, then the separation problem 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 Letchford's algorithm including 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.