Author 
Comment/Response 
Daniel ZS

09/23/10 3:20pm
Are you aware that there are nonCombinatorica form of graphs? They are used with the GraphUtilities package. A form that can be used with connected graphs is simply the specification of the edge set, on the form {e1, e2, e3, ...}, where each edge e is a pair, say e1={v_n,v_m}.
A way to generate your graph would then be to first generate the set of vertices with table, say points=Flatten[Table[{x,y},{x,10},{y,10}],1].
Then do
connectingPoints = Table[
Select[points, SelectFunction], {i,
Length@points}] to make a list of all vertices connected to each point, in order. SelectFunction is a pure function that you can write yourself. I don't know exactly what you mean by 2nd and 3rd nearest neighbours (Do you mean Euclidean or Manhattan metric for example, and do you mean _all_ vertices at that distance and if not how will we distinguish between vertices at the same distance?). But say that you mean all vertices at the closest, 2nd closest and 3rd closest distance of a point to be adjacent to that point. Then SelectFunction could simply be the function Norm[points[[i]]  #] <= maxDist & for some suitable maxDist. That would select all points at or closer than than maxDist.
Then Flatten[Table[
Map[{points[[i]], #} &, connectingPoints[[i]]], {i, Length@points}], 1] will yield the edge set. If you want it to be on Combinatorica form, just do ToCombinatoricaGraph on it (remember to import GraphUtilities.) If you just want to draw it, GraphPlot can take it as an argument directly. ToCombinatoricaGraph can be pretty slow, on the magnitude of minutes for a few tens of thousands of edges. For small and few graphs there's no problem however.
Possibly one could just FunctionalGraph from Combinatorica for all of this, but my first impression was that you would still have to do all of the above, just wrapping it up inside FunctionalGraph. One might of course also make my algorithm more effective, especially the combinings of list (just a quick thought.)
URL: , 
