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的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

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 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.

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 Priority Steiner Tree Problems

优先斯坦纳树问题的近似算法

• 发表时间: 2021
• 期刊: 27th International Computing and Combinatorics Conference (COCOON
• 作者: Spence, R.;Kobourov, S.;Sahneh, F.
• 通讯作者: Sahneh, F.

Graph spanners: A tutorial review

图形扳手：教程回顾

• DOI: 10.1016/j.cosrev.2020.100253
• 发表时间: 2020
• 期刊: Computer Science Review
• 影响因子: 12.9
• 作者: Ahmed, Reyan;Bodwin, Greg;Sahneh, Faryad Darabi;Hamm, Keaton;Latifi Jebelli, Mohammad Javad;Kobourov, Stephen;Spence, Richard
• 通讯作者: Spence, Richard