Dot product representations of planar graphs

Ross J. Kang, László Lovász, Tobias Müller, Edward R. Scheinerman

Research output: Contribution to journalArticleAcademicpeer-review


A graph G is a k -dot product graph if there exists a vector labelling u:V(G)→R k such that u(i) T u(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.
Original languageEnglish
Article numberP216
Number of pages14
JournalElectronic Journal of Combinatorics
Issue number1
Publication statusPublished - 2011
Externally publishedYes


Dive into the research topics of 'Dot product representations of planar graphs'. Together they form a unique fingerprint.

Cite this