Project Details
Projekt
Geometric Representations of Graphs
Subject Area
Theoretical Computer Science
Term
from 2019 to 2024
Project identifier
Deutsche Forschungsgemeinschaft (DFG) - Project number 412962361
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 study two parameters that have recently received increased attention; the maximum crossing number and the ply number.
DFG Programme
Research Grants
International Connection
Czech Republic
Partner Organisation
Czech Science Foundation
Cooperation Partner
Privatdozent Dr. Jiri Fiala, Ph.D.
