3 Search Results for "Schaefer, Marcus"

Document
DOI: 10.4230/LIPIcs.SoCG.2022.41
Short Topological Decompositions of Non-Orientable Surfaces

Authors: Niloufar Fuladi, Alfredo Hubard, and Arnaud de Mesmay

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
We investigate short topological decompositions of non-orientable surfaces and provide algorithms to compute them. Our main result is a polynomial-time algorithm that for any graph embedded in a non-orientable surface computes a canonical non-orientable system of loops so that any loop from the canonical system intersects any edge of the graph in at most 30 points. The existence of such short canonical systems of loops was well known in the orientable case and an open problem in the non-orientable case. Our proof techniques combine recent work of Schaefer-Štefankovič with ideas coming from computational biology, specifically from the signed reversal distance algorithm of Hannenhalli-Pevzner. This result confirms a special case of a conjecture of Negami on the joint crossing number of two embeddable graphs. We also provide a correction for an argument of Negami bounding the joint crossing number of two non-orientable graph embeddings.
Cite as

Niloufar Fuladi, Alfredo Hubard, and Arnaud de Mesmay. Short Topological Decompositions of Non-Orientable Surfaces. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fuladi_et_al:LIPIcs.SoCG.2022.41,
  author =	{Fuladi, Niloufar and Hubard, Alfredo and de Mesmay, Arnaud},
  title =	{{Short Topological Decompositions of Non-Orientable Surfaces}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{41:1--41:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.41},
  URN =		{urn:nbn:de:0030-drops-160492},
  doi =		{10.4230/LIPIcs.SoCG.2022.41},
  annote =	{Keywords: Computational topology, embedded graph, non-orientable surface, joint crossing number, canonical system of loop, surface decomposition}
}
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-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
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-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 Fuladi, Niloufar
  • 1 Fulek, Radoslav
  • 1 Hubard, Alfredo
  • Show More...

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

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

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2008
  • 1 2021
  • 1 2022

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact