CCF-BSF: AF: Small: Metric Embeddings and Partitioning for Minor-Closed Graph Families

算法设计和度量嵌入之间的交互一直是非常富有成效的。在过去的二十年里，度量嵌入工具箱已经成为算法设计者不可或缺的工具箱。原因很简单：嵌入提供了一套简化图和度量空间的技术。这导致了许多图划分和网络设计问题的近似算法。反过来，更好的图分解会带来更好的嵌入。然而，图的拓扑学和度量几何之间的相互作用还没有被完全理解。这项提议的重点是为有趣的图族开发新的技术。更广泛的影响包括让本科生和妇女参与研究，以及培训研究生和博士后助理。此外，拟议中的研究应该有助于在计算机科学和数学之间建立更深层次的联系。作为美国国家科学基金会和美国-以色列双国科学基金会联合倡议的一部分，该项目将加强美国和以色列从事类似课题的研究人员之间的合作。该研究的技术方面集中在平面、有界树宽和路径宽度图以及一般次闭图族的度量嵌入和图划分问题上。这些措施包括通过有界威胁程序为这些家族获得更好的小直径分区，获得更好的L1和树嵌入，以及改进的度量和图压缩技术，例如改进的顶点稀疏器和扳手。

The interaction between algorithm design and metric embeddings has been a very fruitful one. Over the past two decades, the toolbox of metric embeddings has become an indispensable one for the algorithm designer. The reason is simple: embeddings give a set of techniques to simplify graphs and metric spaces. This has led to approximation algorithms for many graph partitioning and network design problems. In turn, better graph decompositions have led to better embeddings. Nevertheless, the interplay between graph topology and the metric geometry is not fully understood. This proposal focuses on developing new techniques for interesting families of graphs. Broader impacts include the engagement of undergraduate students and women in research, and the training of graduate students and postdoctoral associates. Moreover, the proposed research should help develop deeper connections between computer science and mathematics. Being part of a joint initiative between NSF and the US-Israel Binational Science Foundation, this project will increase collaboration between researchers working on similar topics in the United States and Israel.The technical aspects of the research focus on questions in metric embeddings and graph partitioning for planar, bounded tree-width and path-width graphs, and general minor-closed families of graphs. These include getting better low-diameter partitions for these families via the bounded-threatener program, getting better L1 and tree embeddings, and improved metric and graph compression techniques, such as improved vertex-sparsifiers and spanners.