10 citations · 19 across the 18 of their papers we have counts for
4 papers · 1 filter
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…
Which point sets admit a k-angulation?
Michael S. Payne, Jens M. Schmidt, David R. Wood
For k >= 3, a k-angulation is a 2-connected plane graph in which every internal face is a k-gon. We say that a point set P admits a plane graph G if there is a straight-line drawin…
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…