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)