# EECS Publication

Linear-Time Algorithms for Problems on Planar Graphs of Fixed Disk Dimension

Faisal N. Abu-Khzam, Michael A. Langston

The disk dimension of a planar graph G is the least number k for which G embeds in the plane minus k open disks, with every vertex on the boundary of some disk. Useful properties of graphs with a given disk dimension are derived, leading to an efficient algorithm to obtain an outerplanar subgraph of a graph of disk dimension k by removing at most 2k-2 vertices. This reduction is used to obtain linear-time exact and approximation algorithms for problems on graphs of fixed disk dimension. In particular, a linear-time 3-approximation algorithm is presented for the pathwidth problem on graphs of fixed disk dimension. This approximation ratio was previously known only for outerplanar graphs (graphs of disk dimension one).

Published **2005-08-28 04:00:00** as
**ut-cs-05-563 (ID:165)**