Sorting without transitivity

[David Eppstein]

In article <7h3y925o596.fsf at pc150.maths.bris.ac.uk>,
 Michael Hudson <mwh at python.net> wrote:

> Steven Taschuk <staschuk at telusplanet.net> writes:
> 
> > Martelli's already given the magic words "topological sort"; this
> > post is just about the terminology.  (All from memory; corrections
> > welcomed.)
> 
> Do you (or anyone else) know why it's called a *topological* sort?
> Don't see no topology here, off hand.

Graph theory is sometimes considered to be a branch of topology.  The 
usage goes back to at least 1961, when Daniel Lasser published 
"Topological ordering of a list of randomly numbered elements of a 
network" in CACM [4(4):167-168].
http://portal.acm.org/citation.cfm?doid=355578.366314

I found in MathSciNet some earlier papers (Rothe in 1939 and Kyner in 
1956) using the phrase "topological order" to mean something else
(for them, "order" is a number associated with an individual point, 
rather than a way of placing points into a sequence) so I'm guessing the 
phrase comes not out of the mathematical literature but rather out of 
the Navy project to which Lasser refers.

The earlier mathematical phrase for the same concept seems to be "linear 
extension", e.g. Ladislas Fuchs' paper "On the extension of the partial 
order of groups" [Amer. J. Math.  72,  (1950). 191--194] (amusingly 
enough the MathSciNet review of this paper uses "order" in both senses.)

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science