TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Sun, 17 Jan 2021 16:32:14 GMT2021-01-17T16:32:14Z5041Longest Cycles in Cyclically 4-Edge-Connected Cubic Planar Graphshttp://hdl.handle.net/11420/7611Title: Longest Cycles in Cyclically 4-Edge-Connected Cubic Planar Graphs
Authors: Lo, On-Hei Solomon; Schmidt, Jens M.
Abstract: Grünbaum and Malkevitch proved in 1976 that the shortness coefficient of cyclically 4-edge-connected cubic planar graphs is at most 76/77. We prove that it is at most 359/366 (< 52/53).
Mon, 19 Oct 2020 12:28:35 GMThttp://hdl.handle.net/11420/76112020-10-19T12:28:35ZCompact cactus representations of all non-trivial min-cutshttp://hdl.handle.net/11420/7599Title: Compact cactus representations of all non-trivial min-cuts
Authors: Lo, On-Hei Solomon; Schmidt, Jens M.; Thorup, Mikkel
Abstract: Recently, Kawarabayashi and Thorup presented the first deterministic edge-connectivity recognition algorithm in near-linear time. A crucial step in their algorithm uses the existence of vertex subsets of a simple graph G on n vertices whose contractions leave a multigraph with Õ(n∕δ) vertices and Õ(n) edges that preserves all non-trivial min-cuts of G, where δ is the minimum degree of G and Õ hides logarithmic factors. We present a simple argument that improves this contraction-based sparsifier by eliminating the poly-logarithmic factors, that is, we show a contraction-based sparsification that leaves O(n∕δ) vertices and O(n) edges, preserves all non-trivial min-cuts and can be computed in near-linear time Õ(m), where m is the number of edges of G. We also obtain that every simple graph has O((n∕δ)2) non-trivial min-cuts. Our approach allows to represent all non-trivial min-cuts of a graph by a cactus representation, whose cactus graph has O(n∕δ) vertices. Moreover, this cactus representation can be derived directly from the standard cactus representation of all min-cuts in linear time. We apply this compact structure to show that all min-cuts can be explicitly listed in Õ(m)+O(n2∕δ) time for every simple graph, which improves the previous best time bound O(nm) given by Gusfield and Naor.
Mon, 19 Oct 2020 11:12:55 GMThttp://hdl.handle.net/11420/75992020-10-19T11:12:55ZShortness coefficient of cyclically 4-edge-connected cubic graphshttp://hdl.handle.net/11420/7601Title: Shortness coefficient of cyclically 4-edge-connected cubic graphs
Authors: Lo, On-Hei Solomon; Schmidt, Jens M.; Van Cleemput, Nico; Zamfirescu, Carol T.
Abstract: Grünbaum and Malkevitch proved that the shortness coefficient of cyclically 4-edge-connected cubic planar graphs is at most76 77. Recently, this was improved to (Formula Presented) and the question was raised whether this can be strengthened to 42, a natural bound inferred from one of the Faulkner-Younger graphs. We prove that the shortness coefficient of cyclically 4-edge-connected cubic planar graphs is at most 37 38 and that we also get the same value for cyclically 4-edge-connected cubic graphs of genus g for any prescribed genus g ≥ 0. We also show that45 46 is an upper bound for the shortness coefficient of cyclically 4-edge-connected cubic graphs of genus g with face lengths bounded above by some constant larger than 22 for any prescribed g ≥ 0.
Mon, 19 Oct 2020 11:20:20 GMThttp://hdl.handle.net/11420/76012020-10-19T11:20:20ZA cut tree representation for pendant pairshttp://hdl.handle.net/11420/7605Title: A cut tree representation for pendant pairs
Authors: Lo, On-Hei Solomon; Schmidt, Jens M.
Abstract: Two vertices v and w of a graph G are called a pendant pair if the maximal number of edge-disjoint paths in G between them is precisely mind(v), d(w), where d denotes the degree function. The importance of pendant pairs stems from the fact that they are the key ingredient in one of the simplest and most widely used algorithms for the minimum cut problem today. Mader showed 1974 that every simple graph with minimum degree δ contains Ω(δ2) pendant pairs; this is the best bound known so far. We improve this result by showing that every simple graph G with minimum degree δ ≥ 5 or with edge-connectivity λ ≥ 4 or with vertex-connectivity κ ≥ 3 contains in fact Ω(δ|V |) pendant pairs. We prove that this bound is tight from several perspectives, and that Ω(δ|V |) pendant pairs can be computed efficiently, namely in linear time when a Gomory-Hu tree is given. Our method utilizes a new cut tree representation of graphs.
Mon, 19 Oct 2020 11:48:52 GMThttp://hdl.handle.net/11420/76052020-10-19T11:48:52Z