# Graph nomenclature

This concerns graphs that are sets of vertices and edges G={V,E}, not graphical depiction of functions.

Imagine a graph that is a 2D square mesh of vertices. Such a graph can be constructed, for example, by taking typical graph paper, mapping a vertex to each intersection of lines, and an edge to each line segment. The graph paper is thus a visual representation of an abstract graph G. While the visual artifact has spatial attributes (lengths of edges, angles between any three vertices, etc.), G has none of this, only the set of vertices and the set of edges.

Now in the absence of spatial reference, a graph thus derived will have some properties of interest. Most vertices will have 4 neighbors, in fact if V and E are allowed to be infinite, all will have 4 neighbors. And the graph will have planarity. I'm specifically interested in this kind of graph, I.e. ones that have the same properties one would get for those constructed by "copying a 2D mesh". (distinct from the family of graphs that are simply described by "each vertex has 4 neighbor", which could be non planar as the diamond lattice for example)

Is it correct to call the abstract graph G a "2d mesh", or is their a more appropriate name for this construct when explicit spatial attributes are excluded? Question generalizes for "2D triangular mesh", "2D hexagonal mesh".

• Sorry this is a bit of a mess, trying to post from a smartphone. Trying to figure out, is there even a way to describe this kind of graph, without resorting to some visual recerence. May edit soon from a real device. Feb 11, 2014 at 21:59
• As for describing the graph without visual reference, you might say that $V = {\mathbb Z}\times{\mathbb Z}$ (Cartesian product of the integers by themselves) and $E$ consists of all pairs (of pairs) $((m, n), (p, q))$ such that either $m = p$ and $|n-q|=1$ or the other way around.
– DaG
Feb 11, 2014 at 22:13
• Check this out mathworld.wolfram.com/GridGraph.html
– hbm
Feb 11, 2014 at 22:26
• I think what you're looking for is this wikipedia entry: en.wikipedia.org/wiki/Lattice_graph . DaG is describing the unit-distance graph for $\mathbb{Z}^2$, but most everyone would understand what you meant if you said something like the "infinite grid graph". Feb 12, 2014 at 8:53