**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 GraphSearch.

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

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.

Related publications (1)

Related concepts (14)

Related courses (57)

Related MOOCs (11)

Lattice graph

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.

Unit distance graph

In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs.

Path graph

In the mathematical field of graph theory, a path graph (or linear graph) is a graph whose vertices can be listed in the order v_1, v_2, ..., v_n such that the edges are {v_i, v_i+1} where i = 1, 2, ..., n − 1. Equivalently, a path with at least two vertices is connected and has two terminal vertices (vertices that have degree 1), while all others (if any) have degree 2. Paths are often important in their role as subgraphs of other graphs, in which case they are called paths in that graph.

Analyse I

Le contenu de ce cours correspond à celui du cours d'Analyse I, comme il est enseigné pour les étudiantes et les étudiants de l'EPFL pendant leur premier semestre. Chaque chapitre du cours correspond

Analyse I (partie 1) : Prélude, notions de base, les nombres réels

Concepts de base de l'analyse réelle et introduction aux nombres réels.

Analyse I (partie 2) : Introduction aux nombres complexes

Introduction aux nombres complexes

Related lectures (505)

HUM-411: Graphic design II

Le cours vise à faire découvrir les bases du design graphique, ses enjeux, ses différents domaines d'application, ses techniques et ses conventions. Il s'agit d'un enseignement pratique qui repose sur

MATH-101(g): Analysis I

Étudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles d'une variable.

PHYS-117: Physics lab (metrology)

Ce cours est une introduction pratique aux techniques de mesure classiques d'un laboratoire de physique ayant pour but de familiariser les étudiants avec l'acquisition de données, les capteurs, l'anal

Linear Algebra: Matrices and Linear Applications

Covers matrices, linear applications, vector spaces, and bijective functions.

Vector Algebra: Scalar Product

Explores the scalar product of vectors, including properties and calculation methods.

Linear Algebra: Matrix Representation

Explores linear applications in R² and matrix representation, including basis, operations, and geometric interpretation of transformations.

Patrick Thiran, Gergely Odor, Satvik Mehul Mashkaria

The metric dimension (MD) of a graph is a combinatorial notion capturing the minimum number of landmark nodes needed to distinguish every pair of nodes in the graph based on graph distance. We study how much the MD can increase if we add a single edge to the graph. The extra edge can either be selected adversarially, in which case we are interested in the largest possible value that the MD can take, or uniformly at random, in which case we are interested in the distribution of the MD. The adversarial setting has already been studied by [Eroh et. al., 2015] for general graphs, who found an example where the MD doubles on adding a single edge. By constructing a different example, we show that this increase can be as large as exponential. However, we believe that such a large increase can occur only in specially constructed graphs, and that in most interesting graph families, the MD at most doubles on adding a single edge. We prove this for $d$-dimensional grid graphs, by showing that $2d$ appropriately chosen corners and the endpoints of the extra edge can distinguish every pair of nodes, no matter where the edge is added. For the special case of $d=2$, we show that it suffices to choose the four corners as landmarks. Finally, when the extra edge is sampled uniformly at random, we conjecture that the MD of 2-dimensional grids converges in probability to $3+\mathrm{Ber}(8/27)$, and we give an almost complete proof.

2022