Dot Product Representations of Planar Graphs - Kang, Ross J.; Lovász, László; Müller, Tobias; Scheinerman, Edward R. (The Electronic Journal of Combinatorics, 2011)
A graph G is a k-dot product graph if there exists a vector labelling u: V(G) → R^k such that u(i)^Tu(j) ≥ 1 if and only if ij E(G). Fiduccia, Scheinerman, Trenk and Zito [Discrete Math., 1998] 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.