Let $(V,E)$ be a connected, planar graph, and let $S \subset V$ be some desired set of vertices. What is the fastest algorithm, if it exists, to calculate a connected subgraph of $(V,E)$ which contains $S$ and has a minimum number of edges (or, if you like, vertices)? What is its computational complexity?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
Here's how it works:
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
I think you are looking at the Steiner tree problem, or something very similar. There's a huge literature and the wikipedia page seems to be as good a place to start as any. Note that it's NP hard.