  Using a simulated annealing, we examine a bipartitioning of small worlds
obtained by adding a fraction of randomly chosen links to a one-dimensional
chain or a square lattice. Models defined on small worlds typically exhibit a
mean-field behaviour, regardless of the underlying lattice. Our work
demonstrates that the bipartitioning of small worlds does depend on the
underlying lattice. Simulations show that for one-dimensional small worlds,
optimal partitions are finite size clusters for any fraction of additional
links. In the two-dimensional case, we observe two regimes: when the fraction
of additional links is sufficiently small, the optimal partitions have a
stripe-like shape, which is lost for larger number of additional links as
optimal partitions become disordered. Some arguments, which interpret
additional links as thermal excitations and refer to the thermodynamics of
Ising models, suggest a qualitatitve explanation of such a behaviour. The
histogram of overlaps suggests that a replica symmetry is broken in a
one-dimensional small world. In the two-dimensional case, the replica symmetry
seems to hold but with some additional degeneracy of stripe-like partitions.
