10 citations · 19 across the 18 of their papers we have counts for
10 papers · 1 filter
Circumference of essentially 4-connected planar triangulations
Igor Fabrici, Jochen Harant, Samuel Mohr +1
A -connected graph is essentially -connected if, for any -cut of , at most one component of contains at least two vertices. We prove that ev…
Rooted Minors and Locally Spanning Subgraphs
Thomas Böhme, Jochen Harant, Matthias Kriesell +2
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…
Compact Cactus Representations of all Non-Trivial Min-Cuts
On-Hei Solomon Lo, Jens M. Schmidt, Mikkel Thorup
Recently, Kawarabayashi and Thorup presented the first deterministic edge-connectivity recognition algorithm in near-linear time. A crucial step in their algorithm uses the existen…
On the Circumference of Essentially 4-connected Planar Graphs
Igor Fabrici, Jochen Harant, Samuel Mohr +1
A planar graph is essentially -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 essenti…
Longer Cycles in Essentially 4-Connected Planar Graphs
Igor Fabrici, Jochen Harant, Samuel Mohr +1
A planar 3-connected graph is called \emph{essentially -connected} if, for every 3-separator , at least one of the two components of is an isolated vertex. Jackson…
Cut Tree Structures with Applications on Contraction-Based Sparsification
On-Hei Solomon Lo, Jens M. Schmidt
We introduce three new cut tree structures of graphs in which the vertex set of the tree is a partition of and contractions of tree vertices satisfy sparsification requi…