2 Search Results for "Pelsmajer, Michael J."


Document
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-dev.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
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-dev.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}
}
  • Refine by Author
  • 2 Pelsmajer, Michael J.
  • 2 Schaefer, Marcus
  • 1 Fulek, Radoslav
  • 1 Kanj, Iyad A.
  • 1 Xia, Ge

  • Refine by Classification
  • 1 Mathematics of computing → Graphs and surfaces

  • Refine by Keyword
  • 1 Graph Embedding
  • 1 Hanani-Tutte Theorem
  • 1 Induced matching
  • 1 Intersection Form
  • 1 Torus
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2008
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail