Drawing a graph in a hypercube. (English) Zbl 1098.05024
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.
MSC:
05C10 | Planar graphs; geometric and topological aspects of graph theory |
05C62 | Graph representations (geometric and intersection representations, etc.) |
05C78 | Graph labelling (graceful graphs, bandwidth, etc.) |
11B83 | Special sequences and polynomials |
68R10 | Graph theory (including graph drawing) in computer science |