The lattice dimension of a graph
arXiv:cs/0402028 · doi:10.1016/j.ejc.2004.05.001
Abstract
We describe a polynomial time algorithm for, given an undirected graph G, finding the minimum dimension d such that G may be isometrically embedded into the d-dimensional integer lattice Z^d.
6 pages, 3 figures
References in corpus (1)
Cited by in corpus (16)
- Combinatorics and geometry of finite and infinite squaregraphs
- Recognizing Partial Cubes in Quadratic Time
- Steinitz Theorems for Orthogonal Polyhedra
- The lattice dimension of a tree
- Shortest path problem in rectangular complexes of global nonpositive curvature
- On partial cubes, well-graded families and their duals with some applications in graphs
- Isometric embeddings in trees and their use in the diameter problem
- On the Medianwidth of Graphs
- Cops, Robber and Medianwidth Parameters
- Isometric Diamond Subgraphs
- The Fibonacci dimension of a graph
- Cubic Partial Cubes from Simplicial Arrangements
- Algorithms for Drawing Media
- Partial cubes: structures, characterizations, and constructions
- Upright-Quad Drawing of st-Planar Learning Spaces
- Drawing a Graph in a Hypercube