Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Lattice graph
Summary
In graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space \mathbb{R}^n, forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a lattice in the group-theoretical sense.
Typically, no clear distinction is made between such a graph in the more abstract sense of graph theory, and its drawing in space (often the plane or 3D space). This type of graph may more shortly be called just a lattice, mesh, or grid. Moreover, these terms are also commonly used for a finite section of the infinite graph, as in "an 8 × 8 square grid".
The term lattice graph has also been given in the literature to various other kinds of graphs with some regular structure, such as the Cartesian product of a number of complete graphs.
A common type of a lattice graph (known under different names, such as square grid graph) is the graph whose vertices correspond to the points in the plane with integer coordinates, x-coordinates being in the range 1, ..., n, y-coordinates being in the range 1, ..., m, and two vertices are connected by an edge whenever the corresponding points are at distance 1. In other words, it is a unit distance graph for the described point set.
A square grid graph is a Cartesian product of graphs, namely, of two path graphs with n − 1 and m − 1 edges. Since a path graph is a median graph, the latter fact implies that the square grid graph is also a median graph. All square grid graphs are bipartite, which is easily verified by the fact that one can color the vertices in a checkerboard fashion.
A path graph may also be considered to be a grid graph on the grid n times 1. A 2 × 2 grid graph is a 4-cycle.
Every planar graph H is a minor of the h × h grid, where .
Grid graphs are fundamental objects in the theory of graph minors because of the grid exclusion theorem. They play a major role in bidimensionality theory.
A triangular grid graph is a graph that corresponds to a triangular grid.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.