论文标题
在最低度3的1平面图中找到大匹配
Finding large matchings in 1-planar graphs of minimum degree 3
论文作者
论文摘要
匹配是一组没有通用端点的边缘。最近显示，每个1平面图（即，可以在平面上绘制的图形最多可以用每个边缘绘制的图）具有最低度3的最低度尺寸的匹配至少$ \ frac {n+12} {7} {7} $，并且对于某些图而言，这很紧。与通用最大匹配算法相比，证明并未带有算法更有效地找到匹配的算法。在本文中，我们提供了这样的算法。更普遍地，我们表明，任何没有长度为9或更小的增强路径的匹配都具有至少$ \ frac {n+12} {7} $的$ \ frac {n+12} {7} $，其中具有最低度3的1平面图。
A matching is a set of edges without common endpoint. It was recently shown that every 1-planar graph (i.e., a graph that can be drawn in the plane with at most one crossing per edge) that has minimum degree 3 has a matching of size at least $\frac{n+12}{7}$, and this is tight for some graphs. The proof did not come with an algorithm to find the matching more efficiently than a general-purpose maximum-matching algorithm. In this paper, we give such an algorithm. More generally, we show that any matching that has no augmenting paths of length 9 or less has size at least $\frac{n+12}{7}$ in a 1-planar graph with minimum degree 3.
