We consider rules that choose a location on a graph (e.g. a
road network) based on agents' single-peaked preferences.
First, we characterize the class of strategy-proof, onto rules
when the graph is a tree.
Such a rule is based on a collection of generalized
median voter rules (Moulin, 1980) satisfying a consistency condition.
Second, we characterize such rules for graphs containing cycles.
We show that while such a rule is not necessarily dictatorial,
the existence of a cycle grants some agent
an amount of decisive power, unlike the case of trees.
Rules for this case can be described
in terms of a subclass of such rules for trees.
Journal of Economic Literature Classification Numbers: C72, D78.