Given a vertex $u$ (of bounded degree $k$) and another vertex $v$ in a planar graph $G$, what is the smallest number of "curves" in the plane drawn from $u$ to $v$ such that no $u$--$v$ path in $G$ intersects each curve at a point other than $u$ or $v$?
(any finite bound is good as well)
Also, can anyone recommend a reference for graph drawings? Sorry if this is a stupid question.
Unfortunately, there is no finite bound, even if both vertices have bounded degree. To see this, consider a large grid graph $G$ with $u$ a degree-$4$ vertex in the 'left half' of the grid and $v$ a degree-$4$ vertex in the 'right half' of the grid. Let $\mathcal{I}$ be a family of $u$--$v$ curves such that there is no $u$--$v$ path in $G$ which intersects each $I \in \mathcal I$ at a point other than $u$ or $v$.
Let $C$ be the cycle in $G$ consisting of the 'middle' vertical path $P$ of $G$ and the part of the boundary of $G$ to the left of $P$. Since $C$ topologically separates $u$ from $v$, every curve $I \in \mathcal I$ must intersect an edge of $C$ (for this proof, an edge contains its endpoints). Choose such an edge $e(I)$ for each $I \in \mathcal I$. Note that $E(P) \subseteq \{e(I) \mid I \in \mathcal I\}$, because for each $e \in E(P)$, there is a $u$--$v$ path in $G$ using all edges of $E(C) \setminus \{e\}$. Thus, $|\mathcal I| \geq |E(P)|$, which can be arbitrarily large if we increase the size of the grid.
