Planar Graphs Have 1-string Representations

摘要

We prove that every planar graph is an intersection graph of strings in the plane such that any two strings intersect at most once. Keywords Planar graphs - Strings An abstract of this paper appeared in the Proceedings of the eighteenth annual ACM–SIAM Symposium on Discrete algorithms (SODA 2007).