The Isolation Lemma - Finding Longest Cycles in Planar Graphs

Supervisor: Jens M. Schmidt

Imagine you want to find a long cycle in a planar graph G; this is a very classic and well-explored problem in graph theory. A very natural approach to find such a long cycle is to start with a small cycle and attempt to extend it to a longer one. However in this generality such a method is not known so far, but has been recently proposed in this new result [1] about the dynamics of cycles in polyhedra (joint-work with Jan Kessler).

In this master thesis, we aim at strengthening this result in various directions. This thesis therefore needs you to have

  • a profound knowledge of graph theory,
  • interest in structural aspects of graphs, and
  • skill in mathematical writing (preferably in English).

If you are interested in this thesis, please contact me by email.

[1] Jan Kessler and Jens M. Schmidt. Dynamics of Cycles in Polyhedra I: The Isolation Lemma. arXiv, 18.02.2020.

 


 

Betreuer: Jens M. Schmidt

Ein klassisches und wohluntersuchtes Problem aus der Graphentheorie ist, einen längsten Kreis in planaren Graphen zu suchen. Eine naheliegende Methode, um solch einen Kreis zu finden, ist, mit einem kleinen Kreis zu beginnen und diesen schrittweise zu verlängern. Bisher war keine Methode bekannt, die das in dieser Allgemeinheit umsetzt, wurde aber kürzlich in diesem Resultat [1] über die Dynamic von Kreisen in Polyedergraphen gezeigt (joint-work with Jan Kessler).

In dieser Masterarbeit soll dieses Resultat in verschiedene Richtungen verstärkt werden. Diese Masterarbeit benötigt daher

  • Expertise in Graphentheorie,
  • Interesse an den strukturellen Eigenschaften von Graphen, und
  • mathematische Schreibkenntnisse (vorzugsweise auch in Englisch).

Bei Interesse an dieser Arbeit kontaktieren Sie mich bitte per Email.

[1] Jan Kessler and Jens M. Schmidt. Dynamics of Cycles in Polyhedra I: The Isolation Lemma. arXiv, 18.02.2020.