2
$\begingroup$

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".

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – JustJeff
    Feb 11, 2014 at 21:59
  • $\begingroup$ 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. $\endgroup$
    – DaG
    Feb 11, 2014 at 22:13
  • $\begingroup$ Check this out mathworld.wolfram.com/GridGraph.html $\endgroup$
    – hbm
    Feb 11, 2014 at 22:26
  • $\begingroup$ 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". $\endgroup$
    – Casteels
    Feb 12, 2014 at 8:53

1 Answer 1

Reset to default
2
$\begingroup$

As has been mentioned in the comments, the "graph paper" case (either finite or infinite) is a (square) grid/lattice/mesh graph. The generalization you mention at the end can be referred to with the same terminology: triangular/hexagonal grid/lattice/mesh graph. Wolfram has chosen "grid graph" to mean "square grid graph", but wikipedia mentioned all three words.

Be careful, though. The phrase "lattice graph" can also refer to a cartesian product of complete graphs, which is not what you want. Also, The word "lattice" can refer to a type of directed graph related to lattice theory (part of order theory). There are also "lattices" in group theory (better known as "lattice groups") which are related to what you're interested in, but aren't quite what you want.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .