abstract
the sorting number of a graph with n vertices is the minimum depth of a sorting
network with n inputs and n outputs that uses only the edges of the graph to perform
comparisons. many known results on sorting networks can be stated in terms of sorting
numbers of different classes of graphs. in this paper we show the following general
results about the sorting number of graphs.
1. any n-vertex graph that contains a simple path of length d has a sorting network
of depth o(n log(n/d)).
2. any n-vertex graph with maximal degree ∆ has a sorting network of depth o(∆n).
we also provide several results relating the sorting number of a graph with its routing number, size of its maximal matching, and other well known graph properties.
additionally, we give some new bounds on the sorting number for some typical graphs.