JSJens M. Schmidt

Jens M. Schmidt

*This is an algorithmically generated author record based on publicly available information.

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


Jens M. Schmidt has a total of 59 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Rooted minors and locally spanning subgraphs

    by Thomas Böhme, Jochen Harant, Matthias Kriesell, Samuel Mohr, Jens M. Schmidt

    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.


  • Edge-Orders

    by Lena Schlipf, Jens M. Schmidt


  • Open Access

    Computing 2-Walks in Polynomial Time

    by Andreas Schmid, Jens M. Schmidt

    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 ).


  • More on foxes

    by Matthias Kriesell, Jens M. Schmidt

    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.


  • Tight bounds for the vertices of degree k in minimally k‐connected graphs

    by Jens M. Schmidt

    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

    by Andreas Schmid, Jens M. Schmidt

    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.