A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs

A locally connected spanning tree (LCST) T of a graph G is a spanning tree of G such that, for each node, its neighborhood in T induces a connected sub- graph in G. The problem of determining whether a graph contains an LCST or not has been proved to be NP-complete, even if the graph is planar or chordal. The main result of this paper is a simple linear time algorithm that, given a maximal planar chordal graph, determines in linear time whether it contains an LCST or not, and produces one if it exists. We give an anal- ogous result for the case when the input graph is a maximal outerplanar graph.