We give an exact O(nk~2) algorithm for finding the densest k subgraph in outerplanar graphs. We extend this to an exact O(nk~28~b) algorithm for finding the densest k subgraph in b-outerplanar graphs. Often, when there is an exact polynomial time algorithm for a problem on b-outerplanar graphs, this algorithm can be extended to a polynomial time approximation scheme (PTAS) on planar graphs using Baker's technique. We hypothesize that this is not possible for the densest k subgraph problem.
展开▼
