DISCRETE GEOMEMTRY IN THE PLANE WITH GRAPHS

我们主要研究了下面的两个主题，也研究了图表理论中的一些相关主题。给了图表G，在平面上设置了S点，我们想把G放在S上，所以每个G的边缘都是直线段，每个顶点都是S的一个点。如果可能，我们想在没有交叉的情况下找到这样的嵌入，如果不可能在没有交叉的情况下嵌入G，我们想在没有交叉的情况下找到一个小数目的嵌入。我们通过使用图形理论方法和平衡分区方法在这个主题上找到了一些结果。仍有一些未解决的问题令人感兴趣，我们在这一领域开发了结果，另一个研究主题是平衡的分区问题。例如，在平面上给一组红点和一组蓝点，我们想把飞机分成K离散的卷积子集，所以每个子集都包含n_1红点和n_i ×m蓝点，在假设n_1 +... n_k红点和m（n_1 +...+ n_k）蓝点是给定的。如果n_1 =...= n_k，那么这个问题是由我们部分解决的，并由三组研究人员完全解决的。我们在这个问题上发现了更多的一般和相关的结果。“两个问题”有一个关系，“我们wrote a survey entitled”“Discrete Geometry on Red and Blue Points in the Plane-A Survey”，其中包括两个主题为主零件。因此，这些研究领域是新的研究领域，但它们往往是非常迅速的。

We mainly research the following two topics, and also study some related topics in graph theory.For given graph G and set S of points in the plane, we want to embed G onto S so that each edge of G is a straight line segment, and each vertex is a point in S. If possible, we want to find such a embedding without crossings, if it is impossible to embed G onto S without crossings, we want to find a embedding with a small number of crossings.We obtained some results on this topics by using graph theorict method and balanced partition methods. There are still some interesting unsolved problems, our results developed this area.Another research topic is balanced partition problems. Namely, give a set of red points and a set of blue points in the plane, we want to divide the plane into k disjoint convex subsets so that each subset contains n_1 red points and n_i×m blue points under the assumption that n_1 + ・・・n_k red points and m(n_1 + ・・・ + n_k) blue points are given. If n_1 =・・・ =n_k, then this problem was partially solved by us and complete solved by three groups of researchers. We obtained some more general and related results on this problem.The above two problems have a relation ship, and we wrote a survey entitled "Discrete Geometry on Red and Blue Points in the Plane - A Survey", which includes the above two topics as main parts. So these research area are new research area but becomes popular very fast.