A Study of graph decomposition problems

我们证明了以下定理：设$m$为正整数，设$T_1, \cdots, T_q$为$q$断根树，使得$|T_ i| \in \ {m, m+1\} $和$v_i$是所有$ 1\ leqi \ leqq $的$T_i$的根。设$P$是平面上的$|T_1|+ \cdots +|T_q|$点的集合，该平面在一般位置上包含$q$指定点$p_1, \cdots, p_q $。然后根森林$ T_1 \cup \cdots \cup T_q$与根$v_1, \cdots, v_q$可以直线嵌入到$P$上，使得每个$v_i$对应于每$1 \ lei \ leq $的$p_i$。为了证明上述定理，我们证明了下一个定理：设$m$为正整数，设$S_1$、$ S_2$和$T$为平面上三个不相交的点集，使得$S_1 \ S_2 \cup T$没有三个点在同一条线上，且$|T|=(m- 1)|S_1|+ m|S_2|$。放入$q=|S_1 \cup S_2|$。则$S_1 \cup S_2 \cup T$可划分为$q$不相交的子集$P_1, \cdots, P_q$满足以下三个条件：(i) ${\rm \mbox {conv}} \, (P_i) \cap {\rm \mbox {conv}} \, (P_j)= \emptyset $对于所有$1 \leq i<j \leq q$；（ii） S|P_i \cap (S_1 \cup S_2) |=l$ for all $1 \leq i \leq q$；和(3)$ | P_i \帽T | = m - 1如果美元| P_i \帽S_1 | = 1美元,美元| P_i \帽T | = m如果美元| P_i \帽S_2 | = 1美元。这个分区称为半平衡分区。我们的证明给出了一个$0 (n^4) $时间算法，用于寻找阶$n=|T_1|+ \cdots +|T_q|$的根森林$ T_1\cup \cdots \cup T_q$的直线嵌入。

We prove the following theorem : Let $m$ be a positive integer, and let $T_1, \cdots, T_q$ be $q$ disjoint rooted trees such that $|T_ i| \in \ {m, m+1\} $ and $v_i$ is the root of $T_i$ for all $ 1\leq i\leq q$. Let $P$ be a set of $|T_1|+ \cdots +|T_q|$ points in the plane in general position that contains $q$ specified points $p_1, \cdots, p_q $. Then the rooted forest $ T_1 \cup \cdots \cup T_q$ with roots $v_1, \cdots, v_q$ can be straight-line embedded onto $P$ so that each $v_i$ corresponds to $p_i$ for every $1 \le i \le q$.In order to prove the theorem above, we prove the next theorem :Let $m$ be a positive integer and let $S_1$, $ S_2$ and $T$ be three disjoint sets of points in the plane such that no three points of $S_1 \cup S_2 \cup T$ lie on the same lineand $|T|=(m-l)|S_1|+ m|S_2|$. Put $q=|S_1 \cup S_2|$.Then $S_1 \cup S_2 \cup T$ can be partitioned into $q$ disjoint subsets $P_1, \cdots, P_q$ satisfying the following three conditions :(i) ${\rm \mbox {conv}} \, (P_i) \cap {\rm \mbox {conv}} \, (P_j)= \emptyset $ for all $1 \leq i<j \leq q$ ;(ii) S|P_i \cap (S_1 \cup S_2) |=l$ for all $1 \leq i \leq q$ ; and(iii) $|P_i \cap T|=m-1$ if $|P_i \cap S_1|=1$, and $|P_i \cap T|=m$ if $|P_i \cap S_2|=-1$.This partition is called a semi-balanced partition.Our proof gives an $0 (n^4) $ time algorithm for finding the above straight-line embedding of the rooted forest $ T_1\cup \cdots \cup T_q$ of order $n=|T_1|+ \cdots +|T_q|$.