Crossing Number Problems in Geometric Drawings of Graphs

点击翻译按钮获取中文摘要

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. ***