ON HALIN SUBGRAPHS AND SUPERGRAPHS

In this paper, we present two complexity results. The first pertains t o the problem of finding Halin subgraphs while the second is a supergr aph version which asks if a given graph is a subgraph of any Halin gra ph. Both of these problems are shown to be hard which, in turn, provid es somewhat damaging evidence relative to the veracity of heuristic ap proaches employing Halin graphs as approximations.