A. Input, A digraph D. Question: Does D admit an A-handle-decomposition ? It would be nice to characterize the graphs (resp. digraphs) for which A-Ear-Decomposition (resp. A-Handle-Decomposition) is polynomial-time solvable. Below is an easy lemma, that might be useful in proving such a characterization

N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, 1976.

A. Frank, Conservative weightings and ear-decompositions of graphs, Combinatorica, vol.42, issue.2, pp.65-81, 1993.
DOI : 10.1007/BF01202790

M. R. Garey, D. S. Johnson, and L. Stockmeyer, Some simplified NP-complete graph problems, Theoretical Computer Science, vol.1, issue.3, pp.237-267, 1976.
DOI : 10.1016/0304-3975(76)90059-1
URL : https://doi.org/10.1016/0304-3975(76)90059-1

A. Shayan-oveis-gharan, M. Saberi, and . Singh, A randomized rounding approach to the traveling salesman problem, Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp.550-559, 2011.

S. Khuller and U. Vishkin, Biconnectivity approximations and graph carvings, Journal of the ACM, vol.41, issue.2, pp.214-235, 1994.
DOI : 10.1145/174652.174654
URL : http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/jacm94.ps

H. Klauck, On the hardness of global and local approximation, Algorithm Theory ? SWAT'96, pp.88-99, 1996.
DOI : 10.1007/3-540-61422-2_123

L. Lovász, A note on factor-critical graphs, Studia Sci. Math. Hungar, vol.7, pp.279-280, 1972.

T. Mömke and O. Svensson, Approximating Graphic TSP by Matchings, 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp.560-569, 2011.
DOI : 10.1109/FOCS.2011.56

M. Mucha, 13 9 -approximation for Graphic TSP. Theory of Computing Systems, pp.640-657, 2014.
DOI : 10.1007/s00224-012-9439-7
URL : https://hal.archives-ouvertes.fr/hal-00678172

H. E. Robbins, A Theorem on Graphs, with an Application to a Problem of Traffic Control, The American Mathematical Monthly, vol.46, issue.5, pp.281-283, 1939.
DOI : 10.2307/2303897

A. Seb?-o and J. Vygen, Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, 2014.

A. Vetta, Approximating the minimum strongly connected subgraph via a matching lower bound, Proc. 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.417-426, 2001.