<p>Suppose I am given distinct nodes <span class="math-container">$a_1,a_2,.., a_l, r$</span>  and edge disjoint  <span class="math-container">$a_i$</span>-<span class="math-container">$r$</span> paths <span class="math-container">$P_i$</span> for each <span class="math-container">$i$</span> in a planar graph <span class="math-container">$G$</span>.</p>
<p>I wish to construct a tree <span class="math-container">$T$</span>  connecting <span class="math-container">$a_1,a_2,.., a_l, r$</span>  that minimizes the maximum over all <span class="math-container">$a_i$</span> the number of <span class="math-container">$P_i$</span> that an <span class="math-container">$a_i$</span>-<span class="math-container">$r$</span> path of <span class="math-container">$T$</span> shares an edge with.</p>
<p>How small can we guarantee such a quantity is in terms of <span class="math-container">$l$</span>?
That is to say fix <span class="math-container">$l$</span> and consider all possible choices of <span class="math-container">$a_i$</span>-<span class="math-container">$r$</span> paths <span class="math-container">$P_i$</span> how small can we choosing <span class="math-container">$T$</span>, guarantee the maximum over all <span class="math-container">$a_i$</span> the number of <span class="math-container">$P_i$</span> that an <span class="math-container">$a_i$</span>-<span class="math-container">$r$</span> path of <span class="math-container">$T$</span> shares an edge with.</p>

CC BY-SA 4.0
2024-03-08T05:53:08.220Z
Can you explain the question bit more clearly. Do you count the number of edges where $T$ intersects $P$? If yes, isn't the answer unbounded even for $l=1$?
Laakeri
CC BY-SA 4.0
2024-03-08T22:58:29.893Z
@Laakeri  I think you misunderstand I'm not minimizing the number of edges of a   $a_i$-$r$ path  but the number of P_i that it intersects  (where by intersect I mean share an edge)
Hao S
CC BY-SA 4.0
2024-03-10T20:30:06.437Z
This question is not clear at all. It should be rewritten to make it more clear. The way I understand it, the answer can be 0 (because there is a $G$ that contains a tree disjoint from each $P_i$), or the answer can be $l$ (because if $G$ is a star, it contains only one spanning tree).
domotorp
CC BY-SA 4.0
2024-03-11T21:46:54.863Z
@domotorp I clarified that we fix $l$ and consider all possible choices of $a_i$-$r$ paths $P_i$ how small can we guarantee to make...
Hao S
<graph-theory><planar-graphs><tree>
Given $a_i$ -$r$ paths $P_i$ in a planar graph construct a tree spanning $a_i$ such that each root to leaf path intersects few $P_i$
Hao S
# Given $a_i$ -$r$ paths $P_i$ in a planar graph construct a tree spanning $a_i$ such that each root to leaf path intersects few $P_i$

(Asked by: username_0 on 2024-03-07)

Suppose I am given distinct nodes $a\_1,a\_2,.., a\_l, r$ and edge disjoint $a\_i$-$r$ paths $P\_i$ for each $i$ in a planar graph $G$.

I wish to construct a tree $T$ connecting $a\_1,a\_2,.., a\_l, r$ that minimizes the maximum over all $a\_i$ the number of $P\_i$ that an $a\_i$-$r$ path of $T$ shares an edge with.

How small can we guarantee such a quantity is in terms of $l$?
That is to say fix $l$ and consider all possible choices of $a\_i$-$r$ paths $P\_i$ how small can we choosing $T$, guarantee the maximum over all $a\_i$ the number of $P\_i$ that an $a\_i$-$r$ path of $T$ shares an edge with.

**Tags:** graph-theory, planar-graphs, tree
> **Comments:**
> **username_1**: Can you explain the question bit more clearly. Do you count the number of edges where $T$ intersects $P$? If yes, isn't the answer unbounded even for $l=1$?  
> **username_0**: @Laakeri  I think you misunderstand I'm not minimizing the number of edges of a   $a_i$-$r$ path  but the number of P_i that it intersects  (where by intersect I mean share an edge)  
> **username_2**: This question is not clear at all. It should be rewritten to make it more clear. The way I understand it, the answer can be 0 (because there is a $G$ that contains a tree disjoint from each $P_i$), or the answer can be $l$ (because if $G$ is a star, it contains only one spanning tree).  
> **username_0**: @domotorp I clarified that we fix $l$ and consider all possible choices of $a_i$-$r$ paths $P_i$ how small can we guarantee to make...  

---

## 0 answers

