Jens M. Schmidt
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Jens M. Schmidt has a total of 59 co-authors. Here are the top co-authors by number of shared publications:
Kurt Mehlhorn
Max Planck Institute for Informatics
3 shared publicationsAmr Elmasry
COMPUTER SCIENCE DEPARTMENT UNIVERSITY OF COPENHAGEN DENMARK
2 shared publicationsAndreas Schmid
Max Planck Institute for Informatics, Saarbrücken, Germany
2 shared publications- Carola Doerr
Sorbonne Université, CNRS, LIP6
2 shared publications G. Ramakrishna
2 shared publications- Matthias Kriesell
Department of Mathematics Technische Universität Ilmenau Ilmenau Germany
2 shared publications
Latest Publications
- 1 January 2026
- Published by University of Zielona Góra, Poland in Discussiones Mathematicae Graph Theory
- Vol. 46 (3) , 633
Contractible sets in 3-connected planar graphs via Schnyder woods
- 1 January 2026
- Published by University of Zielona Góra, Poland in Discussiones Mathematicae Graph Theory
- Vol. 46 (3) , 633
Contractible sets in 3-connected planar graphs via Schnyder woods
- Open Access
- 16 May 2024
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 173, 329-364
Dynamics of cycles in polyhedra I: The isolation lemma
- 16 May 2024
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 173, 329-364
Open AccessDynamics of cycles in polyhedra I: The isolation lemma
- 20 November 2023
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 165, 47-67
Generalized cut trees for edge-connectivity
- 20 November 2023
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 165, 47-67
Generalized cut trees for edge-connectivity
- 16 August 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 105 (2) , 209-229
Rooted minors and locally spanning subgraphs
Results on the existence of various types of spanning subgraphs of graphs are milestones in structural graph theory and have been diversified in several directions. In the present paper, we consider “local” versions of such statements. In 1966, for instance, D. W. Barnette proved that a 3‐connected planar graph contains a spanning tree of maximum degree at most 3. A local translation of this statement is that if is a planar graph, is a subset of specified vertices of such that cannot be separated in by removing two or fewer vertices of , then has a tree of maximum degree at most 3 containing all vertices of . Our results constitute a general machinery for strengthening statements about ‐connected graphs (for ) to locally spanning versions, that is, subgraphs containing a set of a (not necessarily planar) graph in which only has high connectedness. Given a graph and , we say is a minor of rooted at , if is a minor of such that each bag of contains at most one vertex of and is a subset of the union of all bags. We show that has a highly connected minor rooted at if cannot be separated in by removing a few vertices of . Combining these investigations and the theory of Tutte paths in the planar case yields locally spanning versions of six well‐known results about degree‐bounded trees, Hamiltonian paths and cycles, and 2‐connected subgraphs of graphs.
- 16 August 2023
- Published by Wiley in Journal of Graph Theory
- Vol. 105 (2) , 209-229
Rooted minors and locally spanning subgraphs
Results on the existence of various types of spanning subgraphs of graphs are milestones in structural graph theory and have been diversified in several directions. In the present paper, we consider “local” versions of such statements. In 1966, for instance, D. W. Barnette proved that a 3‐connected planar graph contains a spanning tree of maximum degree at most 3. A local translation of this statement is that if is a planar graph, is a subset of specified vertices of such that cannot be separated in by removing two or fewer vertices of , then has a tree of maximum degree at most 3 containing all vertices of . Our results constitute a general machinery for strengthening statements about ‐connected graphs (for ) to locally spanning versions, that is, subgraphs containing a set of a (not necessarily planar) graph in which only has high connectedness. Given a graph and , we say is a minor of rooted at , if is a minor of such that each bag of contains at most one vertex of and is a subset of the union of all bags. We show that has a highly connected minor rooted at if cannot be separated in by removing a few vertices of . Combining these investigations and the theory of Tutte paths in the planar case yields locally spanning versions of six well‐known results about degree‐bounded trees, Hamiltonian paths and cycles, and 2‐connected subgraphs of graphs.
- 1 May 2018
- Published by Elsevier in Discrete Optimization
- Vol. 28, 63-77
Linear-time recognition of map graphs with outerplanar witness
- 1 May 2018
- Published by Elsevier in Discrete Optimization
- Vol. 28, 63-77
Linear-time recognition of map graphs with outerplanar witness
- Open Access
- 16 April 2018
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 14 (2) , 1-18
Computing 2-Walks in Polynomial Time
A 2-walk of a graph is a walk visiting every vertex at least once and at most twice. By generalizing decompositions of Tutte and Thomassen, Gao, Richter, and Yu proved that every 3-connected planar graph contains a closed 2-walk such that all vertices visited twice are contained in 3-separators. This seminal result generalizes Tutte’s theorem that every 4-connected planar graph is Hamiltonian, as well as Barnette’s theorem that every 3-connected planar graph has a spanning tree with maximum degree at most 3. The algorithmic challenge of finding such a closed 2-walk is to overcome big overlapping subgraphs in the decomposition, which are also inherent in Tutte’s and Thomassen’s decompositions. We solve this problem by extending the decomposition of Gao, Richter, and Yu in such a way that all pieces into which the graph is decomposed are edge-disjoint. This implies the first polynomial-time algorithm that computes the closed 2-walk just mentioned. Its running time is O ( n 3 ).
- 16 April 2018
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 14 (2) , 1-18
Open AccessComputing 2-Walks in Polynomial Time
A 2-walk of a graph is a walk visiting every vertex at least once and at most twice. By generalizing decompositions of Tutte and Thomassen, Gao, Richter, and Yu proved that every 3-connected planar graph contains a closed 2-walk such that all vertices visited twice are contained in 3-separators. This seminal result generalizes Tutte’s theorem that every 4-connected planar graph is Hamiltonian, as well as Barnette’s theorem that every 3-connected planar graph has a spanning tree with maximum degree at most 3. The algorithmic challenge of finding such a closed 2-walk is to overcome big overlapping subgraphs in the decomposition, which are also inherent in Tutte’s and Thomassen’s decompositions. We solve this problem by extending the decomposition of Gao, Richter, and Yu in such a way that all pieces into which the graph is decomposed are edge-disjoint. This implies the first polynomial-time algorithm that computes the closed 2-walk just mentioned. Its running time is O ( n 3 ).
- 8 February 2018
- Published by Wiley in Journal of Graph Theory
- Vol. 89 (2) , 101-114
More on foxes
An edge in a k‐connected graph G is called k‐contractible if the graph obtained from G by contracting e is k‐connected. Generalizing earlier results on 3‐contractible edges in spanning trees of 3‐connected graphs, we prove that (except for the graphs if ) (a) every spanning tree of a k‐connected triangle free graph has two k‐contractible edges, (b) every spanning tree of a k‐connected graph of minimum degree at least has two k‐contractible edges, (c) for , every DFS tree of a k‐connected graph of minimum degree at least has two k‐contractible edges, (d) every spanning tree of a cubic 3‐connected graph nonisomorphic to K4 has at least many 3‐contractible edges, and (e) every DFS tree of a 3‐connected graph nonisomorphic to K4, the prism, or the prism plus a single edge has two 3‐contractible edges. We also discuss in which sense these theorems are best possible.
- 8 February 2018
- Published by Wiley in Journal of Graph Theory
- Vol. 89 (2) , 101-114
More on foxes
An edge in a k‐connected graph G is called k‐contractible if the graph obtained from G by contracting e is k‐connected. Generalizing earlier results on 3‐contractible edges in spanning trees of 3‐connected graphs, we prove that (except for the graphs if ) (a) every spanning tree of a k‐connected triangle free graph has two k‐contractible edges, (b) every spanning tree of a k‐connected graph of minimum degree at least has two k‐contractible edges, (c) for , every DFS tree of a k‐connected graph of minimum degree at least has two k‐contractible edges, (d) every spanning tree of a cubic 3‐connected graph nonisomorphic to K4 has at least many 3‐contractible edges, and (e) every DFS tree of a 3‐connected graph nonisomorphic to K4, the prism, or the prism plus a single edge has two 3‐contractible edges. We also discuss in which sense these theorems are best possible.
- 18 September 2017
- Published by Wiley in Journal of Graph Theory
- Vol. 88 (1) , 146-153
Tight bounds for the vertices of degree k in minimally k‐connected graphs
For minimally k‐connected graphs on n vertices, Mader proved a tight lower bound for the number of vertices of degree k in dependence on n and k. Oxley observed 1981 that in many cases a considerably better bound can be given if is used as additional parameter, i.e. in dependence on m, n, and k. It was left open to determine whether Oxley's more general bound is best possible. We show that this is not the case, but give a closely related bound that deviates from a variant of Oxley's long‐standing one only for small values of m. We prove that this new bound is best possible. The bound contains Mader's bound as special case.
- 18 September 2017
- Published by Wiley in Journal of Graph Theory
- Vol. 88 (1) , 146-153
Tight bounds for the vertices of degree k in minimally k‐connected graphs
For minimally k‐connected graphs on n vertices, Mader proved a tight lower bound for the number of vertices of degree k in dependence on n and k. Oxley observed 1981 that in many cases a considerably better bound can be given if is used as additional parameter, i.e. in dependence on m, n, and k. It was left open to determine whether Oxley's more general bound is best possible. We show that this is not the case, but give a closely related bound that deviates from a variant of Oxley's long‐standing one only for small values of m. We prove that this new bound is best possible. The bound contains Mader's bound as special case.
- Open Access
Computing Tutte Paths
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 inherently use an induction on overlapping subgraphs and these overlaps hinder to bound the running time to a polynomial. For special cases however, computational results of Tutte paths are known: For 4-connected planar graphs, Tutte paths are in fact Hamiltonian paths and Chiba and Nishizeki showed how to compute such paths in linear time. For 3-connected planar graphs, Tutte paths have a more complicated structure, and it has only recently been shown that they can be computed in polynomial time. However, Tutte paths are defined for general 2-connected planar graphs and this is what most applications need. Unfortunately, no computational results are known. We give the first efficient algorithm that computes a Tutte path (for the general case of 2-connected planar graphs). One of the strongest existence results about such Tutte paths is due to Sanders, which allows to prescribe the end vertices and an intermediate edge of the desired path. Encompassing and strengthening all previous computational results on Tutte paths, we show how to compute this special Tutte path efficiently. Our method refines both, the results of Thomassen and Sanders, and avoids overlapping subgraphs by using a novel iterative decomposition along 2-separators. Finally, we show that our algorithm runs in quadratic time.
Open AccessComputing Tutte Paths
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 inherently use an induction on overlapping subgraphs and these overlaps hinder to bound the running time to a polynomial. For special cases however, computational results of Tutte paths are known: For 4-connected planar graphs, Tutte paths are in fact Hamiltonian paths and Chiba and Nishizeki showed how to compute such paths in linear time. For 3-connected planar graphs, Tutte paths have a more complicated structure, and it has only recently been shown that they can be computed in polynomial time. However, Tutte paths are defined for general 2-connected planar graphs and this is what most applications need. Unfortunately, no computational results are known. We give the first efficient algorithm that computes a Tutte path (for the general case of 2-connected planar graphs). One of the strongest existence results about such Tutte paths is due to Sanders, which allows to prescribe the end vertices and an intermediate edge of the desired path. Encompassing and strengthening all previous computational results on Tutte paths, we show how to compute this special Tutte path efficiently. Our method refines both, the results of Thomassen and Sanders, and avoids overlapping subgraphs by using a novel iterative decomposition along 2-separators. Finally, we show that our algorithm runs in quadratic time.