Geometric Representations of Graphs

A graph is a fundamental combinatorial structure that can be used to represent, for a given set of objects (vertices or nodes), which pairs of objects interact with each other (edges). A drawing of a graph is a representation of a graph in the plane (or on some other surface), with vertices typically represented by points, and edges by continuous curves joining their endpoints. Such drawings are called node–link diagrams in the visualization community.

As an alternative to node–link diagrams, one can represent vertices by more complex geometric objects (e.g., circles, rectangles, etc.) and edges either still as curves joining the objects or as a more complex interaction between a pair of objects – for example, as their intersection. These geometric representations of graphs are a fundamental topic in discrete mathematics and computer science due to their frequent occurrence as a way to model real-world problems.

We will study the intersection model and focus on several closely related representation problems: partial representation extension, simultaneous representations, visibility representations with obstacles, H-topological intersection representations. In the area of geometric graphs (node–link diagrams with straight-line edges), we will investigate two parameters that have recently received increased attention; the maximum crossing number and the ply number.