The lattice dimension of a graph

DOI10.1016/j.ejc.2004.05.001zbMath1060.05072arXivcs/0402028OpenAlexW2087412320WikidataQ56210561 ScholiaQ56210561MaRDI QIDQ1775025

David Eppstein

Publication date: 4 May 2005

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0402028

zbMATH Keywords

matchingpolynomial time algorithm

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

The fiber dimension of a graph ⋮ Convex excess in partial cubes ⋮ Optimal strategies in the average consensus problem ⋮ Edge distance-balanced of Hamming graphs ⋮ Partial cubes and their \(\tau\)-graphs ⋮ On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets ⋮ On partial cubes, well-graded families and their duals with some applications in graphs ⋮ Weak sense of direction labelings and graph embeddings ⋮ Structure of Fibonacci cubes: a survey ⋮ On some characterizations of antipodal partial cubes ⋮ Generalized Fibonacci cubes ⋮ On the geodetic number of median graphs ⋮ Algorithms for media ⋮ On distance-balanced graphs ⋮ Isometric Diamond Subgraphs ⋮ Partial cubes: Structures, characterizations, and constructions ⋮ On semicube graphs ⋮ Lattice embeddings of trees ⋮ A poset-based approach to embedding median graphs in hypercubes and lattices ⋮ Induced Embeddings into Hamming Graphs. ⋮ Transitive, locally finite median graphs with finite blocks ⋮ Netlike partial cubes, V: completion and netlike classes ⋮ Induced cycles in crossing graphs of median graphs

Cites Work

• Retracts of strong products of graphs
• Isometric embedding in products of complete graphs
• A canonical decomposition theory for metrics on a finite set
• Media theory
• On the complexity of recognizing Hamming graphs and related classes of graphs
• Distance-preserving subgraphs of hypercubes
• Embedding Topological Median Algebras in Products of Dendrons
• Recognizing binary Hamming graphs inO(n 2 logn) time
• Paths, Trees, and Flowers
• Unnamed Item
• Unnamed Item
• Unnamed Item