On the disk dimension of planar graphs

Abstract

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 of the disks. Disk dimension finds application in circuit layout and related fields. For every fixed k, the family of ``yes'' instances is closed under minors and excludes a planar graph. Thus graphs of disk dimension k or less are in principle (but not constructively) recognizable in linear time.

In this paper, we study instead constructive techniques to decide the disk dimension problem. We prove that a graph of disk dimension k has treewidth at most 2k, and is thus amenable to an approach based on dynamic programming for fixed-width tree decompositions. More significantly, we devise a direct and highly practical linear-time algorithm to decide whether an arbitrary graph has fixed disk dimension k or less. We also discuss it's efficiency and implementation.

Finally we investigate the pathwidth approximation strategy proposed for outerplanar graphs by Govindan, Langston and Yan in 1998. We demonstrate that it can be used in this setting to obtain a practical, linear-time pathwidth heuristic for graphs of bounded disk dimension. We prove that this fast heuristic, when given a graph of pathwidth p and fixed disk dimension k, will produce a path decomposition whose width is at most 3p+2k-2.