Computing tutte paths
A Schmid, JM Schmidt - arXiv preprint arXiv:1707.05994, 2017 - arxiv.org
Tutte paths are one of the most successful tools for attacking Hamiltonicity problems in
planar graphs. Unfortunately, results based on them are non-constructive, as their proofs …
planar graphs. Unfortunately, results based on them are non-constructive, as their proofs …
Dynamics of cycles in polyhedra I: the isolation lemma
J Kessler, JM Schmidt - Journal of Combinatorial Theory, Series B, 2024 - Elsevier
A cycle C of a graph G is isolating if every component of G− V (C) consists of a single vertex.
We show that isolating cycles in polyhedral graphs can be extended to larger ones: every …
We show that isolating cycles in polyhedral graphs can be extended to larger ones: every …
On the circumference of essentially 4-connected planar graphs
I Fabrici, J Harant, S Mohr… - Journal of graph …, 2020 - jgaa-v4.cs.brown.edu
A planar graph is essentially $4 $-connected if it is 3-connected and every of its 3-separators
is the neighborhood of a single vertex. Jackson and Wormald proved that every essentially 4 …
is the neighborhood of a single vertex. Jackson and Wormald proved that every essentially 4 …
On the circumference of essentially 4-connected planar graphs
I Fabrici, J Harant, S Mohr, JM Schmidt - arXiv preprint arXiv:1806.09413, 2018 - arxiv.org
A planar graph is essentially $4 $-connected if it is 3-connected and every of its 3-separators
is the neighborhood of a single vertex. Jackson and Wormald proved that every essentially 4 …
is the neighborhood of a single vertex. Jackson and Wormald proved that every essentially 4 …
Plane and simple: using planar subgraphs for efficient algorithms
A Schmid - 2019 - publikationen.sulb.uni-saarland.de
In this thesis, we showcase how planar subgraphs with special structural properties can be
used to fi nd efficient algorithms for two NP-hard problems in combinatorial optimization. In …
used to fi nd efficient algorithms for two NP-hard problems in combinatorial optimization. In …