In a Python plotting application,
I have an undirected connected graph, not necessarily simple, that I'd like to cover with paths such that each edge is contained in exactly one path.
The number of nodes/edges will typically be a few hundred or a few thousand. One solution is to create a new path for every edge, but that's a little too rough. Ideally I'd find the minimum number of paths, but I get the notion that this might be NP-hard (see the Hamiltonian path problem, traveling salesman problem, this question etc.). Any practical heuristic is good enough.
Any hints?