The disk dimension problem was introduced by Fellows and Langston in 1987. The disk dimension of a graph, G, is the least k for which G embeds in the plane minus k open disks, with every vertex of G on a boundary of one ...