Intersection number of two connected geometric graphs

被引：18

作者：

Tokunaga, S

机构：

[1] Department of Applied Mathematics, Tokyo Ikashika University, Kounodai, Ichikawa

来源：

INFORMATION PROCESSING LETTERS | 1996年 / 59卷 / 06期

关键词：

combinatorial problems; finite points in the plane; geometric graphs;

D O I：

10.1016/0020-0190(96)00124-X

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Let S be a finite set of points in the plane in general position such that each point of S is colored red or blue. In this paper, we solve the following problem: find two geometric spanning trees of the blue and the red points such that they intersect in as few points as possible. We also prove that there are two paths, one connecting the blue points and the other connecting the red points such that any edge of each of them intersects the other at most once.

引用

页码：331 / 333

页数：3