Geometric Representations of Graphs

图的几何表示

• 批准号: 412962361
• 负责人: Professor Dr. Ignaz Rutter
• 金额: --
• 依托单位: Lehrstuhl für Theoretische Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2019
• 资助国家: 德国
• 起止时间: 2018-12-31 至 2023-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/412962361?language=en
• 关键词: Geometric; Representations; 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 study two parameters that have recently received increased attention; the maximum crossing number and the ply number.

图是一种基本的组合结构，可以用来表示，对于一组给定的对象（顶点或节点），哪些对对象相互作用（边）。图形的绘制是平面（或其他表面）上图形的表示，其中顶点通常由点表示，边由连接其端点的连续曲线表示。在可视化社区中，这样的绘图被称为节点链接图。作为节点链接图的替代方案，可以用更复杂的几何对象（例如圆形，矩形等）表示顶点。而边或者仍然作为连接对象的曲线，或者作为一对对象之间的更复杂的相互作用-例如，作为它们的交点。这些图的几何表示是离散数学和计算机科学中的一个基本课题，因为它们经常出现作为一种建模现实世界的问题。我们将研究交集模型，并专注于几个密切相关的表示问题：部分表示扩展，同时表示，可见性表示与障碍，H-拓扑交集表示。在几何图形（直线边的节点链接图）领域，我们将研究最近受到越来越多关注的两个参数：最大交叉数和层数。