The Dimension of Signed Graph Valid Drawings


A signed graph is a graph with a sign assignment to their edges. Drawing a signed graph in Rk means finding an embedding of the set of nodes into Rk such that, for each node, all its positive neighbors (friends) are closer than its negative neighbors (enemies). This work addresses the problem of finding L (n), the smallest dimension k such that any graph on n nodes has a valid drawing in Rk, with respect to euclidean distance. We show that L (n)= n− 2 by demonstrating that any graph on n nodes can be embedded in Rn− 2 and that there exists a signed graph on n nodes that does not have a valid drawing in Rn− 3.

Submitted to Discrete Computational Geometry