DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2021.38

Strong Hanani-Tutte for the Torus

Authors: Radoslav Fulek, Michael J. Pelsmajer, and Marcus Schaefer

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract

If a graph can be drawn on the torus so that every two independent edges cross an even number of times, then the graph can be embedded on the torus.

Cite as

Radoslav Fulek, Michael J. Pelsmajer, and Marcus Schaefer. Strong Hanani-Tutte for the Torus. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fulek_et_al:LIPIcs.SoCG.2021.38,
  author =	{Fulek, Radoslav and Pelsmajer, Michael J. and Schaefer, Marcus},
  title =	{{Strong Hanani-Tutte for the Torus}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{38:1--38:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.38},
  URN =		{urn:nbn:de:0030-drops-138378},
  doi =		{10.4230/LIPIcs.SoCG.2021.38},
  annote =	{Keywords: Graph Embedding, Torus, Hanani-Tutte Theorem, Intersection Form}
}

Document

DOI: 10.4230/LIPIcs.STACS.2008.1361

On the Induced Matching Problem

Authors: Iyad A. Kanj, Michael J. Pelsmajer, Ge Xia, and Marcus Schaefer

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract

We study extremal questions on induced matchings in several natural graph classes. We argue that these questions should be asked for twinless graphs, that is graphs not containing two vertices with the same neighborhood. We show that planar twinless graphs always contain an induced matching of size at least $n/40$ while there are planar twinless graphs that do not contain an induced matching of size $(n+10)/27$. We derive similar results for outerplanar graphs and graphs of bounded genus. These extremal results can be applied to the area of parameterized computation. For example, we show that the induced matching problem on planar graphs has a kernel of size at most $40k$ that is computable in linear time; this significantly improves the results of Moser and Sikdar (2007). We also show that we can decide in time $O(91^k + n)$ whether a planar graph contains an induced matching of size at least $k$.

Cite as

Iyad A. Kanj, Michael J. Pelsmajer, Ge Xia, and Marcus Schaefer. On the Induced Matching Problem. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 397-408, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{kanj_et_al:LIPIcs.STACS.2008.1361,
  author =	{Kanj, Iyad A. and Pelsmajer, Michael J. and Xia, Ge and Schaefer, Marcus},
  title =	{{On the Induced Matching Problem}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{397--408},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1361},
  URN =		{urn:nbn:de:0030-drops-13618},
  doi =		{10.4230/LIPIcs.STACS.2008.1361},
  annote =	{Keywords: Induced matching, bounded genus graphs, parameterized algorithms, kernel}
}

Search Results

Documents authored by Schaefer, Marcus

Strong Hanani-Tutte for the Torus

Abstract

Cite as

On the Induced Matching Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message