The Densest k Subgraph Problem in b-Outerplanar Graphs

Abstract

We give an exact $O(n{k}^2)$ algorithm for finding the densest k subgraph in outerplanar graphs. We extend this to an exact $O(n{k}^2{8}^b)$ algorithm for finding the densest k subgraph in b-outerplanar graphs. Finally, we hypothesize that Baker's PTAS technique will not work for the densest k subgraph problem in planar graphs.