10 citations · 19 across the 18 of their papers we have counts for
8 papers · 1 filter
Dynamics of Cycles in Polyhedra I: The Isolation Lemma
Jan Kessler, Jens M. Schmidt
A cycle of a graph is \emph{isolating} if every component of is a single vertex. We show that isolating cycles in polyhedral graphs can be extended to larger ones:…
Computing Tutte Paths
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 i…
Mondshein Sequences (a.k.a. (2,1)-Orders)
Jens M. Schmidt
Canonical orderings [STOC'88, FOCS'92] have been used as a key tool in graph drawing, graph encoding and visibility representations for the last decades. We study a far-reaching ge…
Certifying 3-Edge-Connectivity
Kurt Mehlhorn, Adrian Neumann, Jens M. Schmidt
We present a certifying algorithm that tests graphs for 3-edge-connectivity; the algorithm works in linear time. If the input graph is not 3-edge-connected, the algorithm returns a…
A Simple Test on 2-Vertex- and 2-Edge-Connectivity
Jens M. Schmidt
Testing a graph on 2-vertex- and 2-edge-connectivity are two fundamental algorithmic graph problems. For both problems, different linear-time algorithms with simple implementations…
A Planarity Test via Construction Sequences
Jens M. Schmidt
Optimal linear-time algorithms for testing the planarity of a graph are well-known for over 35 years. However, these algorithms are quite involved and recent publications still try…