Solving Crossing Number Problems With Applications

University Of North Texas, Denton TX

Investigators

Abstract

A drawing of a graph is a one-to-one placement of the vertices and edges into the plane so that the edges become continuous curves. Many important problems in theory of VLSI and computational geometry can be stated as graph drawing problems. For instance, the problem minimizing the number of edge crossings, or the crossing number problem, has been extensively studied in theory of VLSI. Moreover, a class of interesting problems in discrete and computational geometry exhibit structures which can viewed as variations, generalizations and extensions of the notion of crossings. Some of these problems can be reformulated as problems concerning cliques, independent sets and the chromatic numbers of the intersection graphs of drawings. In addition, automatic generation of drawings is customary in many scientific areas in which diagrammatic representations are used. Most of these problems are computationally difficult, and therefore it only makes sense to focus on the design of approximation algorithms for solving them. Unfortunately, geometric properties of many such problems are not well understood, and additional research is needed to investigate the design of new and effective approximation algorithms, or to sharpen and improve the performance of the existing algorithms for solving them. This project is aimed at studying a collection of problems that arise in drawings of graphs in the plane. The theoretical goal is to develop new structural results and theoretically efficient approximation algorithms that can produce provably near optimal solutions. The experimental goal is to implement these algorithms and test and document their effectiveness in practice.