  This paper defines the toroidal small world labeling problem that asks for a
labeling of the vertices of a network such that the labels possess information
that allows a compact routing scheme in the network. We consider the problem
over a small world network model we propose. Both the model and the compact
routing scheme have applications in peer-to-peer networks. The proposed model
is based on the model of Kleinberg (2000), and generates an undirected
two-dimensional torus with one random long-range edge per vertex. These random
edges create forbidden cycles that mimic the underlying torus topology, and
this behavior confuses attempts for extracting the routing information from the
network. We show that such forbidden cycles happen with small probability,
allowing us to use a breadth-first search that finds the vertices positions on
the torus. The positions are pairs of integer numbers that provides routing
information to a greedy routing algorithm that finds small paths of the
network. We present a linear time labeling algorithm that detects and removes
the random edges, finds the underlying torus and labels almost all vertices
through a breadth-first search. The labeling algorithm is then used by a
compact routing scheme for the proposed small world model.
