Dot product representations of planar graphs (Q648410)

Summary: A graph \(G\) is a \(k\)-dot product graph if there exists a vector labelling \(u : V (G) \rightarrow \mathbb R^k\) such that \(u(i)^T u(j) \geq 1\) if and only if \(ij \in E(G)\). \textit{C. M. Fiduccia} et al. [Discrete Math. 181, No. 1--3, 113--138 (1998; Zbl 0974.05058)] asked whether every planar graph is a 3-dot product graph. We show that the answer is ``no''. On the other hand, every planar graph is a 4-dot product graph. We also answer the corresponding questions for planar graphs of prescribed girth and for outerplanar graphs.