Crossing Number Problems in Geometric Drawings of Graphs

图形几何绘图中的交叉数问题

• 批准号: 9528228
• 负责人: Farhad Shahrokhi
• 金额: $ 4.81万
• 依托单位: University of North Texas
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-06-15 至 1999-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9528228&HistoricalAwards=false
• 关键词: Crossing; Number; Problems; Geometric; Drawings

Geometric drawings give rise to many interesting and important problems which are the extensions, generalizations, or the dual forms of the well known planar crossing problem. A k-crossing in a geometric drawing is defined to be a set of k edges which pairwise cross in the drawing. An interesting problem here is to generate geometric drawings with small number of k-crossings, for a given graph and a given k1. Another important problem is the crossing clique problem, in which the objective is to generate geometric drawings so that the largest clique of crossings (the largest k so that the drawing has a k-crossing) is small. This problem is closely related to the page number problem and has nice applications to the theory of VLSI. The dual concept to a k- crossing is a k-disjoint set: Given a geometric drawing of the G, a k-disjoint set is a set of k edges which are pairwise non- crossing in the drawing. The concept of k-disjoint sets gives rise to problems which are similar to those of k-crossings, in a dual setting. It is the goal of this investigation to study k- crossings, k-disjoint sets, and the crossing clique problem. The aim is to develop algorithms which can generate solutions whose quality can be guaranteed and/or to develop general structural results in a form which could be applicable to a broad class of graphs. ***

几何作图中产生了许多有趣而重要的问题，它们是平面相交问题的推广、推广或对偶形式。 几何图形中的k-交叉被定义为图形中成对交叉的k条边的集合。 这里一个有趣的问题是，对于给定的图和给定的k1，生成具有少量k-交叉的几何图形。 另一个重要的问题是交叉团问题，其中的目标是生成几何图形，使得交叉的最大团（最大k，使得图形具有k交叉）很小。 该问题与页数问题密切相关，在VLSI理论中有很好的应用。 k-交叉的对偶概念是k-不相交集：给定G的几何图，k-不相交集是图中成对不交叉的k条边的集合。 k-不相交集的概念在对偶环境中产生了与k-交叉类似的问题。 本文主要研究k-交叉、k-不交集和交叉团问题。 我们的目的是开发算法，可以产生的解决方案，其质量可以得到保证和/或开发一般结构的结果，在一种形式，可以适用于广泛的一类图。 ***