权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

DISCRETE GEOMEMTRY IN THE PLANE WITH GRAPHS

平面上的离散几何图形

基本信息

批准号：
12640102
负责人：
KANO Mikio
金额：
$ 1.66万
依托单位：
IBARAKI UNIVERSITY
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2000
资助国家：
日本
起止时间：
2000 至 2001
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-12640102/
关键词：
Geometric Graph Geometry in the Plane Graph Embedding Balanced Partition Perfect Partition Graph Theory 幾何的グラフ凸集合直線埋め込み 2色点集合の分割

项目摘要

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.

本文主要研究以下两个问题，同时也研究了图论中的一些相关问题：对于给定的图G和平面上的点集S，我们想把G嵌入到S上，使得G的每条边都是直线段，每个顶点都是S中的一个点。如果可能的话，我们希望找到这样一个没有交叉的嵌入，如果不可能把G无交叉地嵌入到S上，我们希望找到一个有少量交叉的嵌入，我们利用图论方法和平衡划分方法得到了这方面的一些结果.还有一些有趣的问题没有解决，我们的结果发展了这一领域。另一个研究课题是平衡划分问题。即给定平面上的一组红点和一组蓝点，在给定n_1 + ···nk个红点和m（n_1+ ··· +nk）个蓝点的假设下，将平面划分为k个不相交的凸子集，使得每个子集包含n_1个红点和n_1 ×m个蓝点。如果n_1 =··· =n_k，则我们部分解决了这个问题，三组研究人员完全解决了这个问题。这两个问题是有联系的，我们写了一个综述，题目是“Discrete Geometry on Red and Blue Points in the Plane - A Survey”，其中主要包括这两个题目。因此，这些研究领域是新兴的研究领域，但发展很快.