Induced matchings in subcubic planar graphs

R.J. Kang, M. Mnich, T. Muller

Research output: Contribution to journalArticleAcademicpeer-review

11 Citations (Scopus)
190 Downloads (Pure)


We present a linear-time algorithm that, given a planar graph with m edges and maximum degree 3, finds an induced matching of size at least m/9. This is best possible
Original languageEnglish
Pages (from-to)1383-1411
JournalSIAM Journal on Discrete Mathematics
Issue number3
Publication statusPublished - 2012


Dive into the research topics of 'Induced matchings in subcubic planar graphs'. Together they form a unique fingerprint.

Cite this