Drawing a graph in a hypercube

zbMATH Open1098.05024arXivmath/0509455MaRDI QIDQ2500992FDOQ2500992

David R. Wood

Publication date: 30 August 2006

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

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.

Full work available at URL: https://arxiv.org/abs/math/0509455

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

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

zbMATH Keywords

Sidon setsantimagic injectionshypercube drawing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) 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)

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)