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

项目成果

期刊论文数量（41）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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
通讯作者：
Mark Wallinger;Benjamin N. Jacobsen;S. Kobourov;M. Nöllenburg

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

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

DOI：
发表时间：
2019
期刊：
Symposium on Experimental Algorithms
影响因子：
0
作者：
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 树问题的近似算法

DOI：
发表时间：
2019
期刊：
ArXiv.org
影响因子：
0
作者：
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
影响因子：
0
作者：
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
影响因子：
0
作者：
Ahmed, R;Bodwin, G;Darabi, F;Kobourov, S;Spence, R
通讯作者：
Spence, R