# Sample algorithm to “linearize” a graph

Simplifying a business example, I have the following situation:

Some objects should be distributed in a graph in most "linear" way possible for a given "thermometer".

Say, a voyager visits some cities. Several cities are visited multiple times.

So, we have list of cities in ordinate axis (that may be duplicated), and Time in abscissas one.

Now, for a given path, say (A => X => A => B => C) we should display a line, in the "most linear way possible".

By eg. in the image above, the green line is optimal one
(1 > 2 > 3 > 4 > 5)

but there could be multiple possible outputs

(1 > 2 > 1 > 4 > 5)
(1 > 2 > 3 > 4 > 5)
(1 > 2 > 6 > 4 > 5)

(3 > 2 > 1 > 4 > 5)
(3 > 2 > 3 > 4 > 5)
(3 > 2 > 6 > 4 > 5)

(6 > 2 > 1 > 4 > 5)
(6 > 2 > 3 > 4 > 5)
(6 > 2 > 6 > 4 > 5)

Is there some algorithms helping in such situations?

-
Is it not more linear to move the first point up to (1)? Maybe I do not understand the requirements. With repeats you can always construct your graph so that any given sequence or path is displayed linearly. – Joshua Shane Liberman Jan 25 '11 at 15:11
@Joshua Shane Liberman: Have reason. I fixed the post. – serhio Jan 25 '11 at 17:28
Your edits have made my statement even more valid and left unanswered. The algorithm is to have the ordinate axis be your list of visited cities. Are you asking if one graph can make all possible outputs appear linear? – Joshua Shane Liberman Jan 25 '11 at 17:47
@Joshua Shane Liberman: The problem is that the Thermometer is modified by the user, and not generated by the graph nodes. – serhio Jan 25 '11 at 18:13
I don't understand the question, and the lack of responses suggests I'm not the only one. Voting to close in the hope of spurring OP on to edit some comprehensibility into the question. – Gerry Myerson Jul 24 '11 at 5:02