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

DOI10.1007/s11083-011-9203-7zbMath1237.05133OpenAlexW2026771827MaRDI 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

hypercubesisometric embeddingslatticesmedian graphsmedian semilatticesisometric dimensionlattice dimension

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

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