Drawing a graph in a hypercube

MaRDI QIDQ2500992zbMATH OpenFDO

Authors David R. Wood

Publication date 30 August 2006

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0509455, https://eudml.org/doc/126512, http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1r73.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

antimagic injectionshypercube drawingSidon sets

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Special sequences and polynomials (11B83) Graph theory (including graph drawing) in computer science (68R10)

Abstract: A $d$-dimensional hypercube drawing of a graph represents the vertices by distinct points in ${0,1}^d$, such that the line-segments representing the edges do not cross. We study lower and upper bounds on the minimum number of dimensions in hypercube drawing of a given graph. This parameter turns out to be related to Sidon sets and antimagic injections.

Review text

Summary: A \(d\)-dimensional hypercube drawing of a graph represents the vertices by distinct points in \(\{0,1\}^d\), such that the line-segments representing the edges do not cross. We study lower and upper bounds on the minimum number of dimensions in hypercube drawing of a given graph. This parameter turns out to be related to Sidon sets and antimagic injections.

Recommendations

• The cubicity of hypercube graphs
• An improved upper bound on the crossing number of the hypercube
• An improved upper bound on the crossing number of the hypercube.
• Bounds for the crossing number of the N‐cube
• A survey of the theory of hypercube graphs

Cited in

(2)

• Harmonious order of graphs
• Limitations on realistic hyperbolic graph drawing

This page was built for publication: Drawing a graph in a hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2500992)