Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428433 | Information Processing Letters | 2007 | 5 Pages |
Abstract
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 algorithm to obtain an outerplanar subgraph of a graph with disk dimension k by removing at most 2k−2 vertices. This reduction is used to obtain linear-time exact and approximation algorithms on graphs with fixed disk dimension. In particular, a linear-time approximation algorithm is presented for the pathwidth problem.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics