Witness Proximity Graphs

Abstract

Proximity graphs are used in several areas in which a neighborliness relationship for input data sets is a useful tool in their analysis. They have also received substantial attention from the graph drawing community, being a natural way of implicitly representing graphs.

In this talk, WITNESS GRAPHS, a framework generalizing proximity graphs, will be introduced. We present witness versions of the Gabriel graph, Delaunay graph and rectangular influence graph, and some efficient algorithms to compute them.

We also demonstrate some forbidden subgraphs in order to achieve a partial characterization of the new families of graphs, and give a complete characterization of the square graphs.

If time allows, we will present some related results about stabbing disks, squares and rectangles in the plane.

Bio: Muriel Dulieu is in her last year as a Ph.D. student in computer science at The Polytechnic Institute of New York University. She is doing her Ph.D. thesis with Prof. Boris Aronov on "Witness Proximity Graphs and Other Geometric Problems." Previously she received degrees in psychology and in computer science from the Free University of Brussels, where she wrote a thesis on epsilon-nets under the supervision of Dr. Stefan Langerman.