加载中…
Recently the authors [CCLMST23] introduced the notion of shortcut partition of planar graphs and obtained several results from the partition, including a tree cover with trees for planar metrics and an additive embedding into small treewidth graphs. In this note, we apply the same partition to resolve the Steiner point removal (SPR) problem in planar graphs: Given any set of terminals in an arbitrary edge-weighted planar graph , we construct a minor of whose vertex set is , which preserves the shortest-path distances between all pairs of terminals in up to a constant factor. This resolves in the affirmative an open problem that has been asked repeatedly in literature.

生成讲解博客的中文版本

生成AI智能校验的中文版本