Finding big matchings in planar graphs quickly

MaRDI QIDQ6314375zbMATH OpenFDO

Authors Therese Biedl

Publication date 20 February 2019

Abstract: It is well-known that every $n$-vertex planar graph with minimum degree 3 has a matching of size at least $fracn3$. But all proofs of this use the Tutte-Berge-formula for the size of a maximum matching. Hence these proofs are not directly algorithmic, and to find such a matching one must apply a general-purposes maximum matching algorithm, which has run-time $O(n^{1.5}alpha(n))$ for planar graphs. In contrast to this, this paper gives a linear-time algorithm that finds a matching of size at least $fracn3$ in any planar graph with minimum degree 3.

This page was built for publication: Finding big matchings in planar graphs quickly

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6314375)