Topical Studies in Graph and Matroid Theory

图是一种数学抽象，用来对结构进行建模，表现出一种“离散”的性质。例如通信和运输网络、乘务调度、车辆路线、计算机芯片设计和数字设备。拟阵是比图更抽象的结构，对于理解几何、刚性和优化问题的良好算法至关重要。我的研究试图了解这种结构的基本属性，目的是优化各种感兴趣的参数。例如，在电影节上为场馆分配放映时间的问题可以被建模为一种图着色问题。我们知识的进步可以导致调度算法的改进。随着数字通信的出现，这种研究对于有效设计和部署新兴技术至关重要。用更专业的语言，组成这项建议的三个项目如下：-几个长长的边选择列表：对于可以嵌入平面的图，问题是从预先分配的列表中找到避免颜色冲突的边的颜色选择。-面向着色的拟阵：图着色的概念可以通过两种不同的方式扩展到几何对象。我们比较了这两个扩展的属性，以及它们所承载的信息。-高次顶点较少的三角化曲面的分类：三角化曲面是计算机绘制曲面的中心。我们研究了某些类型的此类曲面，这些曲面与标准三角剖分仅略有偏离，其中六条边在每个顶点相交。

Graphs are mathematical abstractions which are used to model structures exhibiting a "discrete" nature. Examples include communication and transportation networks, crew scheduling, vehicle routing, computer chip design and digital devices. Matroids are structures which are more abstract than graphs, which are vital to the understanding of geometry, rigidity, and good algorithms for optimization problems. My research seeks to understand fundamental properties of such structures, with an aim toward optimizing various parameters of interest. For example, the problem of assigning shows to venues at a film festival can be modeled as a type of graph colouring problem. Advances in our knowledge can lead to improved scheduling algorithms. With the advent of digital communication such studies are vital to the efficient design and deployment of arising technologies. In more technical language, three of the projects comprising this proposal are as follows.- Few Long Lists for Edge Choosability: For graphs that can be embedded in the plane, the problem is to find a selection of colours for the edges, from preassigned lists, that avoid colour conflicts.- Colouring Oriented Matroids: The notion of graph colouring can be extended to geometric objects in two different ways. We compare properties of the two extensions, and the information that they carry.- Classification of Triangulated Surfaces with Few High-degree Vertices: Triangulated surfaces are central to computer rendering of surfaces. We investigate certain classes of such surfaces which deviate only slightly from canonical triangulations, where six edges meet at each vertex.