Every graph admits an unambiguous bold drawing
János Pach
Vol. 19, no. 1, pp. 299-312, 2015. Regular paper.
Abstract Let r and w be fixed positive numbers, w < r. In a bold drawing of a graph, every vertex is represented by a disk of radius r, and every edge by a narrow rectangle of width w. We solve a problem of van Kreveld  by showing that every graph admits a bold drawing in which the region occupied by the union of the disks and rectangles representing the vertices and edges does not contain any disk of radius r other than the ones representing the vertices.
Submitted: August 2013.
Reviewed: March 2014.
Revised: February 2015.
Accepted: February 2015.
Final: June 2015.
Published: June 2015.
Communicated by Stephen G. Kobourov
article (PDF)