Abstract

A signed graph is an undirected graph with a sign assignment to its edges. Drawing a signed graph in Rk means finding an injection of the set of nodes into Rk. A valid distance drawing of a signed graph in Rk is an injection of the nodes into Rk such that, for each node, all its positive neighbors are closer than its negative neighbors. This work addresses the problem of finding L(n), the smallest dimension such that any graph on n nodes has a valid distance drawing in a Euclidean space of dimension L(n). We show that [log5(n- 3)] + 1 <= L(n) =<= n- 2. We also compute exact values for L(n) up to n = 7.