Yes, Seldom, that is exactly what GPSMapEdit is doing for me! I am aware of the colored squares representing routing nodes, with different colors indicating the number of connections.
I just added several polylines to one of my maps yesterday, some of which were linked to existing polylines, and GPSMapEdit adds the routing nodes to each polyline as I create them.
After adding a dozen or so, I wanted to test them, so I selected one section of a pre-existing polyline as a start point and selected a newly added polyline as an end point, and GPSMapEdit successfully routed old and new lines correctly. I tested in reverse, starting at a new line and ending at old lines, with same results, then only along new lines, and same result.
Update: Just tested the new map on my GPSr, and the new polylines also route properly on the GPSr as well!
I have not performed a new map verification or generated a new routing graph for the current *.img export.