1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.