AF:Small:Geometric and Combinatoric Algorithms for Contact and Intersection Representation of Graphs

AF:Small：图的接触和交集表示的几何和组合算法

• 批准号: 1712119
• 负责人: Stephen Kobourov
• 金额: $ 44.91万
• 依托单位: University of Arizona
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2022-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1712119&HistoricalAwards=false
• 关键词: AF; Small; Geometric; Combinatoric; Algorithms

Networks of nodes connected by links are a useful abstraction in many areas -- from sociology and biology to engineering and transportation. Networks are used to model causal structures, hierarchies, and scheduling. Although networks are typically drawn as node-link diagrams, several areas use geometric representations of networks (molecules in chemistry or floor-plans in engineering). This project explores intersection and contact representation of networks, where nodes are geometric objects (e.g., rectangles, segments) and links are realized by intersections (e.g., segments crossing) or contacts between the objects (e.g., rectangular duals). A geometric representation is more than just a way to display the network; it reveals underlying combinatorial structures which can often be described only using geometry. The goal of this project is to leverage these connections and build new bridges between geometry and combinatorics, in order to develop algorithms for intersection and contact representations of networks, with broader impact in information visualization, network analysis, and computational cartography. Educational activities, such as new coursework development, graduate and undergraduate student advising and outreach are integral parts of this project. Finally, continuing the investigator's tradition of implementing new algorithms and deploying software, dissemination of results will not only be accomplished by publishing in scientific journals, organizing workshops and seminars, but also by making software and data available.The specific research agenda is to identify connections between geometry and combinatorics in the context of intersection and contact representations of graphs. As a result of studying the classes of graphs that can be represented as contacts between simple polygons (e.g., triangles and quadrilaterals), the combinatorial properties of these graph classes will be used to design algorithms for constructing such representations. Efficient algorithms will be designed and implemented for constructing proportional (value-by-area) contact representations and for creating static and dynamic cartograms. These problems are addressed on two fronts: (a) by finding necessary and sufficient conditions for specific types of intersection and contact representation, developing new representation algorithms, and establishing tight bounds for the problems; and (b) by directly applying the theoretical results to practical problems in information visualization and cartography, as well as implementing and experimentally evaluating the new methods, which are made available as fully functional online systems.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.

通过链接连接的节点网络在许多领域都是有用的抽象 - 从社会学和生物学到工程和运输。网络用于建模因果结构，层次结构和计划。尽管网络通常是作为节点链接图绘制的，但几个领域使用网络的几何表示（化学分子或工程中的地板分子）。该项目探讨了网络的交叉点和接触表示，其中节点是几何对象（例如矩形，段），并且链接通过交集（例如，片段交叉）或对象之间的接触（例如，矩形双值）来实现。几何表示不仅仅是显示网络的一种方式。它揭示了基本的组合结构，通常只能使用几何形状来描述。该项目的目的是利用这些连接并在几何和组合之间建立新的桥梁，以开发用于网络相交和接触表示的算法，并在信息可视化，网络分析和计算制图中产生更大的影响。教育活动，例如新的课程发展，毕业和本科生建议和外展活动是该项目不可或缺的一部分。 最后，继续研究者实施新算法和部署软件的传统，结果不仅可以通过在科学期刊上发布，组织研讨会和研讨会来实现，还可以通过制作软件和数据来实现。具体的研究议程是在几何学和组合之间的连接中确定与图形和接触形式的相关形式之间的联系。通过研究可以表示为简单多边形（例如三角形和四边形）之间接触的图类别的结果，这些图类别的组合特性将用于设计用于构建此类表示形式的算法。有效的算法将被设计和实施，用于构建比例（逐个区域的价值）触点表示以及创建静态和动态摄影图。这些问题在两个方面解决：（a）通过为特定类型的交叉路口和接触表示，开发新的表示算法并为问题建立紧密的界限来解决必要的条件； （b）直接将理论结果直接应用于信息可视化和制图的实际问题，以及实施和实验评估新方法，这些方法可作为功能齐全的在线系统提供。该奖项反映了NSF的法定任务，并通过使用该基金会的智力功能和广泛的影响来评估Criteria，并通过评估来评估NSF的法定任务。

项目成果

On the Readability of Abstract Set Visualizations

• DOI: 10.1109/tvcg.2021.3074615
• 发表时间: 2021-01
• 期刊: IEEE Transactions on Visualization and Computer Graphics
• 影响因子: 5.2
• 作者: Mark Wallinger;Benjamin N. Jacobsen;S. Kobourov;M. Nöllenburg

Approximation algorithms and an integer program for multi-level graph spanners

多级图扳手的近似算法和整数程序

• 发表时间: 2019
• 期刊: Symposium on Experimental Algorithms
• 作者: Ahmed, R.;Hamm, K.;Jebelli, M.;Kobourov, S.;Sahneh, F.;Spence, R.
• 通讯作者: Spence, R.

Approximation algorithms for the vertex-weighted grade-of-service Steiner tree problem

顶点加权服务等级 Steiner 树问题的近似算法

• 发表时间: 2019
• 期刊: ArXiv.org
• 作者: Ahmed, R.;Efrat, A.;Kobourov, S.;Krieger, S.;Spence, R.
• 通讯作者: Spence, R.

The Segment Number: Algorithms and Universal Lower Bounds for Some Classes of Planar Graphs

线段数：某些类平面图的算法和通用下界

• DOI: 10.1007/978-3-031-15914-5_20
• 发表时间: 2022
• 期刊: 48th International Workshop on Graph-Theoretic Concepts in Computer Science (WG
• 作者: Goessmann, I.;Klawitter, J.;Klemz, B.;Klesen, F.;Kobourov, S.;Kryven, M.;Wolff, A.;Zink, J.
• 通讯作者: Zink, J.

Weighted Additive Spanners

加权附加扳手

• DOI: 10.1007/978-3-030-60440-0_32
• 发表时间: 2020
• 期刊: 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG
• 作者: Ahmed, R;Bodwin, G;Darabi, F;Kobourov, S;Spence, R
• 通讯作者: Spence, R