Finding Large Matchings in 1-Planar Graphs of Minimum Degree 3

Therese Biedl, Fabian Klute

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

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 n+127 , 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 n+127 in a 1-planar graph with minimum degree 3.

F. Klute—This work was conducted while FK was a member of the “Algorithms and Complexity Group” at TU Wien.

Research of TB supported by NSERC. Research initiated while FK was visiting the University of Waterloo.
Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, Revised Selected Papers
EditorsIsolde Adler, Haiko Müller
PublisherSpringer
Pages248-260
Number of pages13
ISBN (Electronic)978-3-030-60440-0
ISBN (Print)978-3-030-60439-4
DOIs
Publication statusPublished - 2020

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12301
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Dive into the research topics of 'Finding Large Matchings in 1-Planar Graphs of Minimum Degree 3'. Together they form a unique fingerprint.

Cite this