A poset-based approach to embedding median graphs in hypercubes and lattices

DOI10.1007/s11083-011-9203-7zbMath1237.05133MaRDI QIDQ766140

Christine T. Cheng

Publication date: 23 March 2012

Published in: Order (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11083-011-9203-7

zbMATH Keywords

hypercubes; isometric embeddings; lattices; median graphs; median semilattices; isometric dimension; lattice dimension

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C65: Hypergraphs

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

There are no finite partial cubes of girth more than 6 and minimum degree at least 3, Covering partial cubes with zones

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weak sense of direction labelings and graph embeddings
• Median graphs, parallelism and posets
• Isometric embedding in products of complete graphs
• Exactly solvable discrete BCS-type Hamiltonians and the six-vertex model
• Lattice embeddings of trees
• Planar graphs and poset dimension
• Recognizing median graphs in subquadratic time
• The lattice dimension of a graph
• Graphs of some CAT(0) complexes
• Distance-preserving subgraphs of hypercubes
• Rings of sets
• A decomposition theorem for partially ordered sets
• Stable Roommates Matchings, Mirror Posets, Median Graphs, and the Local/Global Median Phenomenon in Stable Matchings
• Note on Dilworth's Decomposition Theorem for Partially Ordered Sets
• Metric Ternary Distributive Semi-Lattices
• On Isometric Embeddings of Graphs
• Stable networks and product graphs