Do you need for the strings to be readable?   (In other words, to quote Mary Poppins, supercali...docious?)   If so, maybe you just want to take the first x characters and the last ycharacters and separate them with an elipses.   If you find that the name collides with something you already have, add a couple of random digits.   (Or, for consistency, just do that all the time.)

If you don’t need them to be readable, a short string of randomly-selected characters can be generated, and a hash used to link the literal string to the random moniker that you have thusly chosen.

If you “know” that some parts of the URLs you’ll be dealing with are never “interesting to anybody,” just omit them entirely.

If there might be some ambiguity in the user’s mind when looking at a particular graph vs. similar ones, consider adding a legend to the graph or in a separate document.   It also might be desirable to simply, say, number the elements on your graph, then provide a separate legend in all cases.

If you intend to produce many graphs that you know will be compared side by side and that you also know will contain many “similars,” consider using (say...) an SQLite database file to maintain a consistent mapping table that grows as necessary.