论文标题
最短的路径覆盖了非交叉的四个森林
Non-Crossing Shortest Paths are Covered with Exactly Four Forests
论文作者
论文摘要
给定一组路径$ p $，我们定义了\ emph {路径覆盖$ p $}（$ p $}（pcfn（$ p $）），这是一组$ f $ f $ f $的最小尺寸，使$ p $中的每条路径都包含在$ f $中的至少一个森林中。我们表明，当$ p $是平面图或子类中的一组非交叉的最短路径时，PCFN（$ p $）是可以治疗的。我们证明，如果$ p $是一组非划线的平面图$ g $的最短路径，其极端顶点位于$ g $的同一面上，则PCFN（$ p $）\ leq 4 $，并且这种界限很紧。
Given a set of paths $P$ we define the \emph{Path Covering with Forest Number} of $P$} (PCFN($P$)) as the minimum size of a set $F$ of forests satisfying that every path in $P$ is contained in at least one forest in $F$. We show that PCFN($P$) is treatable when $P$ is a set of non-crossing shortest paths in a plane graph or subclasses. We prove that if $P$ is a set of non-crossing shortest paths of a planar graph $G$ whose extremal vertices lie on the same face of $G$, then PCFN($P$)\leq 4$, and this bound is tight.
