Converting all arcs to polygonal arcs in a plane graph

99 Views Asked by At

I am trying to understand a proof on the conversion of arcs to polygonal arcs in plane graphs, in the book "Graphs on Surfaces" by Mohar and Thomassen. In the book, an arc joining two points $x,y \in \mathbb{R}^2$ is an injective continuous function $f : [0,1] \to \mathbb{R}^2$ with $x = f(0), y = f(1)$. A polygonal arc is an arc whose image is the union of a finite number of straight line segments.

Specifically, here are the parts I don't understand, which I would appreciate enlightenment on:

  1. Given an open set $U \subseteq \mathbb{R}^2$ and $x, y \in U$, suppose we have an arc $f$ joining $x,y$ contained within $U$. Suppose we know that the open balls $\{B_{r_1}(x_1),\dots,B_{r_k}(x_k)\}$ (where $x_i \in f([0,1])$) are contained in $U$ and cover $f([0,1])$. How can we explicitly construct a polygonal arc connecting $x$ and $y$ contained in the union $B_{r_1}(x_1) \cup \dots \cup B_{r_k}(x_k)$?

  2. Suppose we have disjoint closed sets $F_1$ and $F_2$ in $\mathbb{R}^2$. Suppose we have an arc $f$ from an element of $F_1$ to an element of $F_2$. How can we find a segment of the arc connecting an element of $F_1$ to an element of $F_2$ with no intermediate point in common with $F_1 \cup F_2$? Here a segment is $f([a,b])$ where $0 \leq a < b \leq 1$.

1

There are 1 best solutions below

0
On BEST ANSWER

For 2.: Around each point $t\in[0,1]$ such that $f(t)\in V:=\mathbb{R}^2\setminus(F_1\cup F_2)$, you can take a maximal open interval $(c_1,c_2)$ such that $f((c_1,c_2))\subseteq V$ (since $V$ is open). By maximality, we have that $f(c_1),f(c_2)\in F_1\cup F_2$.

Now take $a$ to be the $\sup$ of all the endpoints $c$ such that $f(c)\in F_1$. This must be less than $1$, otherwise $f(1)\in F_1$. Now take $b$ to be the $\inf$ of all the endpoints $c$ such that $c>a$ and $f(c)\in F_2$. By continuity, $f(a)\in F_1$ and $f(b)\in F_2$. I claim that the interval $(a,b)$ satisfies the requirement. Indeed, by construction there can be no intervals $(c_1,c_2)$ properly included in $(a,b)$, so either its image by $f$ is disjoint from $V$ (contradicting the fact that $F_1\cap F_2=\emptyset$) or $(a,b)$ is one of the maximal intervals.

For 1., I think that the main idea is to take the line segments joining the centers of the balls, but the details of this approach might messy.