The Lattice Dimension of a Graph

Title: The Lattice Dimension of a Graph

Research Question: Can we find the minimum number of dimensions needed to represent a graph on a lattice?

Methodology: The researchers used a polynomial time algorithm to find the minimum lattice dimension for an undirected graph. They considered embedding the graph into a d-dimensional integer lattice, Zd, such that the distance between two vertices is equal to the L1-distance between their coordinates.

Results: They found that the lattice dimension of any graph that can be isometrically embedded into the d-dimensional integer lattice can be found in polynomial time.

Implications: This research has implications for graph algorithms, graph structure, and graph visualization. It provides insights into the geometric representations of graphs and the isometric embeddings of graphs into hypercubes. The results can be used to develop new algorithms and data structures for graphs with finite lattice dimensions.

Summary: This research proposes a polynomial time algorithm for finding the minimum lattice dimension for an undirected graph. It considers embedding the graph into a d-dimensional integer lattice and uses the concept of isometric embeddings to determine the minimum dimension. The results have implications for graph algorithms, graph structure, and graph visualization, and can be used to develop new data structures for graphs with finite lattice dimensions.

Link to Article: https://arxiv.org/abs/0402028v1 Authors: arXiv ID: 0402028v1