Welcome to Fnd2012 Open Problems, where you can ask questions and receive answers from other members of the community.

How to remove Steiner points from planar metrics?

0 votes

Given a planar graph G with some k vertices marked red (or "required") and the remaining blue (called "Steiner"), let d be the shortest path metric on G. Can you give a planar graph H just on the red vertices so that distances between red vertices in G and H are within a constant multiplicative factor of each other?

Prior relevant work: If G is a tree, or an outerplanar graph, this problem is solved (see here, here), and the constant of 8 for trees is tight. If G is an arbitrary planar graph, we know how to give a distribution over planar graphs H (in fact, over minors of G) such that the expected distance between every pair of vertices in this distribution is within a constant of that in G.

Variants: what if we allow some O(k) Steiner points to remain in the graph? what if we allow H to be non-planar, yet only have O(k) edges? [I'll add some references here soon.]

asked Jul 31, 2012 by anupam (120 points)

1 Answer

0 votes

Some related construction is in Subramianian PhD. If you are given a planar graph where k terminals lie on the external face, then there exists an epsilon-approximate substitute of size O(epsilon^-1 k log k log D), where D is the diameter of the graph. This is described in Section 2.1.

answered Aug 1, 2012 by sank (180 points)