Collaborative Research: AF: Medium: Algorithms for Geometric Graphs

合作研究：AF：媒介：几何图算法

• 批准号: 2212130
• 负责人: Stephen Kobourov
• 金额: $ 40.02万
• 依托单位: University of Arizona
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-06-15 至 2026-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2212130&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Medium; Algorithms

This project studies geometric graphs. These are geometric structures that realize the relationships of a combinatorial graph, that is, a set of elements called “nodes” or “vertices” and a set of pairwise relationships between them, such as would be determined by a social network or road network. Geometric graphs arise in a wide range of applications, including physics, data visualization, computational biology, and data forensics. Any such graph can be realized in a geometric space, so that the nodes of the graph are points in the space and relationships between nodes are represented by line segments or curves connecting pairs of nodes. These geometric realizations of combinatorial graphs can then be measured in terms of how well they achieve various parameters, such as area, edge length, angle separation, etc. Indeed, the research area of graph drawing is exclusively focused on algorithms for producing good (faithful and representative) geometric realizations of graphs. Improved methods for dealing with geometric graphs can benefit any application, such as data visualization or automobile navigation, that generates or uses geometric graphs.The goals of this project are broadly organized around the following two themes: (1) Algorithms for producing geometric realizations of graphs. This theme is directed at algorithms and complexity bounds for producing geometric realizations of graphs, including considerations of complexity measures such as area, edge length, edge bends, edge crossings, etc. (2) Algorithms on geometric graphs. This theme is directed at algorithms that take as input geometric graphs, such as road networks, with the goal of achieving complexity bounds that are improved over those possible for general graphs.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

该项目研究几何图，这些几何结构实现了组合图的关系，即一组称为“节点”或“顶点”的元素以及它们之间的一组成对关系，例如由社交网络或道路网络。几何图出现在广泛的应用中，包括物理学、数据可视化、计算生物学和数据取证。任何这样的图都可以在几何空间中实现，因此图的节点是其中的点。节点之间的空间和关系由连接节点对的线段或曲线表示。然后可以根据它们实现各种参数的程度来测量，例如面积、边长、角度间隔等。事实上，组合图的研究领域图形绘制专门关注生成良好（忠实且有代表性）图形几何实现的算法。处理几何图形的改进方法可以使任何生成或使用几何图形的应用程序受益，例如数据可视化或汽车导航。这个项目广泛围绕以下两个主题组织： (1) 用于生成图的几何实现的算法 该主题针对用于生成图的几何实现的算法和复杂性界限，包括对面积、边长、边弯曲、边等复杂性度量的考虑。 (2) 几何图算法 该主题针对以道路网络等输入几何图的算法，其目标是实现比一般图可能的复杂度界限有所改进。该奖项。通过使用基金会的智力价值和更广泛的影响审查标准进行评估，NSF 的法定使命被认为值得支持。

项目成果

An FPT Algorithm for Bipartite Vertex Splitting

一种二分顶点分裂的FPT算法

• 发表时间: 2022
• 期刊: 30th International Symposium on Graph Drawing and Network Visualization (GD
• 作者: Ahmed, R.;Kobourov, S.;Kryven, M.
• 通讯作者: Kryven, M.

2D, 2.5D, or 3D? An Exploratory Study on Multilayer Network Visualisations in Virtual Reality

2D、2.5D 还是 3D？

• DOI: 10.1109/tvcg.2023.3327402
• 发表时间: 2024
• 期刊: IEEE Transactions on Visualization and Computer Graphics
• 影响因子: 5.2
• 作者: Feyer, Stefan P.;Pinaud, Bruno;Kobourov, Stephen;Brich, Nicolas;Krone, Michael;Kerren, Andreas;Behrisch, Michael;Schreiber, Falk;Klein, Karsten
• 通讯作者: Klein, Karsten

Multi-Priority Graph Sparsification

多优先级图稀疏化

• 发表时间: 2023
• 期刊: 34th Intl. Workshop on Combinatorial Algorithms (IWOCA
• 作者: Ahmed, R.;Hamm, K.;Kobourov, S.;Jebelli, M.;Sahneh, F.;Spence, R
• 通讯作者: Spence, R

Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem

最大双峰子图问题的参数化和逼近算法

• 发表时间: 2024
• 期刊: 31st International Symposium on Graph Drawing and Network Visualization (GD
• 作者: Didimo, Walter;Fomin, Fedor;Golovach, Petr;Inamdar, Tanmay;Kobourov, Stephen;Sieper, Marie
• 通讯作者: Sieper, Marie

The Influence of Dimensions on the Complexity of Computing Decision Trees

维数对计算决策树复杂度的影响

• 发表时间: 2023
• 期刊: 37th AAAI Conference on Artificial Intelligence (AAAI
• 作者: Kobourov, S.;Loffler, M.;Montecchiani, F.;Pilipczuk, M;Rutter, I.;Seidel, R.;Sorge, M.
• 通讯作者: Sorge, M.