TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Fri, 21 Jan 2022 01:15:23 GMT2022-01-21T01:15:23Z50491- Counting K₄-Subdivisionshttp://hdl.handle.net/11420/7629Title: Counting K₄-Subdivisions
Authors: Miltzow, Tillmann; Schmidt, Jens M.; Xia, Mingji
Abstract: A fundamental theorem in graph theory states that any 3-connected graph contains a subdivision of K₄. As a generalization, we ask for the minimum number of K₄-subdivisions that are contained in every 3-connected graph on n vertices. We prove that there are Ω(n³) such K₄-subdivisions and show that the order of this bound is tight for infinitely many graphs. We further investigate a better bound in dependence on m and prove that the computational complexity of the problem of counting the exact number of K₄-subdivisions is #P-hard.
Wed, 21 Oct 2020 16:27:53 GMThttp://hdl.handle.net/11420/76292020-10-21T16:27:53Z
- Linear-time recognition of map graphs with outerplanar witnesshttp://hdl.handle.net/11420/7612Title: Linear-time recognition of map graphs with outerplanar witness
Authors: Mnich, Matthias; Rutter, Ignaz; Schmidt, Jens M.
Abstract: Map graphs generalize planar graphs and were introduced by Chen, Grigni and Papadimitriou [STOC 1998, J.ACM 2002]. They showed that the problem of recognizing map graphs is in NP by proving the existence of a planar witness graph W. Shortly after, Thorup [FOCS 1998] published a polynomial-time recognition algorithm for map graphs. However, the run time of this algorithm is estimated to be Ω(n120) for n-vertex graphs, and a full description of its details remains unpublished. We give a new and purely combinatorial algorithm that decides whether a graph G is a map graph having an outerplanar witness W. This is a step towards a first combinatorial recognition algorithm for general map graphs. The algorithm runs in time and space O(n + m). In contrast to Thorup's approach, it computes the witness graph W in the affirmative case.
Mon, 19 Oct 2020 12:46:50 GMThttp://hdl.handle.net/11420/76122020-10-19T12:46:50Z
- Mondshein sequences (A.K.A. (2; 1)-orders)http://hdl.handle.net/11420/7614Title: Mondshein sequences (A.K.A. (2; 1)-orders)
Authors: Schmidt, Jens M.
Abstract: Canonical orderings have been used as a key tool in graph drawing, graph encoding, and visibility representations for the last decades [H. de Fraysseix, J. Pach, and R. Pollack, Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC '88), ACM, New York, 1988, pp. 426-433; G. Kant, Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS '92), IEEE Press, Piscataway, NJ, 1992, pp. 101-110]. We study a far-reaching generalization of canonical orderings to nonplanar graphs that was published by Lee Mondshein in a Ph.D. thesis as early as 1971. Mondshein proposed to order the vertices of a graph in a sequence such that for any i, the vertices from 1 to i essentially induce a 2-connected graph, while the remaining vertices from i+1 to n induce a connected graph. Mondshein's sequence generalizes canonical orderings and later became independently known as nonseparating ear decomposition. Surprisingly, this fundamental link between canonical orderings and nonseparating ear decomposition had not been previously established. Currently, the fastest known algorithm for computing a Mondshein sequence achieves a running time of O(nm); the main open problem in Mondshein's and follow-up work is to improve this running time to subquadratic time. After putting Mondshein's work into context, we present an algorithm that computes a Mondshein sequence in optimal time and space O(m). This improves the previous best running time by a factor of n. We illustrate the impact of this result by deducing linear-time algorithms for five other problems-in four of these, the previous best running time was quadratic. In particular, we show how to compute three independent spanning trees in a 3-connected graph in time O(m), improving a result of Cheriyan and Maheshwari [J. Algorithms, 9 (1988), pp. 507-537]; improve the preprocessing time from O(n2) to O(m) for the output-sensitive data structure of Di Battista, Tamassia, and Vismara [Algorithmica, 23 (1999), pp. 302-340] that reports three internally disjoint paths between any given vertex pair; derive a very simple O(n)-time planarity test once a Mondshein sequence is computed; compute a nested family of contractible subgraphs of 3-connected graphs in time O(m); and compute a 3-partition in time O(m) (the previous best running time is O(n2) due to Suzuki et al. [Information Processing Society of Japan (IPSJ), 31 (1990), pp. 584-592 (in Japanese)]).
Mon, 19 Oct 2020 13:03:52 GMThttp://hdl.handle.net/11420/76142020-10-19T13:03:52Z
- An O(n+ m) certifying triconnnectivity algorithm for Hamiltonian graphshttp://hdl.handle.net/11420/7641Title: An O(n+ m) certifying triconnnectivity algorithm for Hamiltonian graphs
Authors: Elmasry, Amr; Mehlhorn, Kurt; Schmidt, Jens M.
Abstract: A graph is triconnected if it is connected, has at least 4 vertices and the removal of any two vertices does not disconnect the graph. We give a certifying algorithm deciding triconnectivity of Hamiltonian graphs with linear running time (this assumes that the cycle is given as part of the input). If the input graph is triconnected, the algorithm constructs an easily checkable proof for this fact. If the input graph is not triconnected, the algorithm returns a separation pair.
Thu, 22 Oct 2020 09:30:29 GMThttp://hdl.handle.net/11420/76412020-10-22T09:30:29Z
- Every DFS tree of a 3-connected graph contains a contractible edgehttp://hdl.handle.net/11420/7639Title: Every DFS tree of a 3-connected graph contains a contractible edge
Authors: Elmasry, Amr; Mehlhorn, Kurt; Schmidt, Jens M.
Thu, 22 Oct 2020 09:12:36 GMThttp://hdl.handle.net/11420/76392020-10-22T09:12:36Z
- More on foxeshttp://hdl.handle.net/11420/7594Title: More on foxes
Authors: Kriesell, Matthias; Schmidt, Jens M.
Abstract: An edge in a k-connected graph G is called k-contractible if the graph G/e 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 ��Kk��+1 if �� ∈ 1, 2) (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 3/2 k-1 has two k-contractible edges, (c) for k>3, every DFS tree of a k-connected graph of minimum degree at least 3/2k-3/2 has two k-contractible edges, (d) every spanning tree of a cubic 3-connected graph nonisomorphic to K4 has at least 1/3|V(G)|-1 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.
Mon, 19 Oct 2020 07:49:30 GMThttp://hdl.handle.net/11420/75942020-10-19T07:49:30Z
- Computing 2-walks in polynomial timehttp://hdl.handle.net/11420/7630Title: Computing 2-walks in polynomial time
Authors: Schmid, Andreas; Schmidt, Jens M.
Abstract: © 2015 LIPICS. 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, in which the graph is decomposed into, are edge-disjoint. This implies the first polynomial-time algorithm that computes the closed 2-walk mentioned above.
Wed, 21 Oct 2020 16:35:06 GMThttp://hdl.handle.net/11420/76302020-10-21T16:35:06Z
- Cubic plane graphs on a given point sethttp://hdl.handle.net/11420/7631Title: Cubic plane graphs on a given point set
Authors: Schmidt, Jens M.; Valtr, Pavel
Abstract: Let P be a set of n≥4 points in the plane that is in general position and such that n is even. We investigate the problem whether there is a (0-, 1- or 2-connected) cubic plane straight-line graph on P. No polynomial-time algorithm is known for this problem. Based on a reduction to the existence of certain diagonals of the boundary cycle of the convex hull of P, we give the first polynomial-time algorithm that checks for 2-connected cubic plane graphs; the algorithm is constructive and runs in time O(n3). We also show which graph structure can be expected when there is a cubic plane graph on P; e. g., a cubic plane graph on P implies a connected cubic plane graph on P, and a 2-connected cubic plane graph on P implies a 2-connected cubic plane graph on P that contains the boundary cycle of P. We extend the above algorithm to check for arbitrary cubic plane graphs in time O(n3).
Wed, 21 Oct 2020 16:42:08 GMThttp://hdl.handle.net/11420/76312020-10-21T16:42:08Z
- Which point sets admit a k-angulation?http://hdl.handle.net/11420/7592Title: Which point sets admit a k-angulation?
Authors: Payne, Michael Stuart; Schmidt, Jens M.; Wood, David R.
Abstract: 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 drawing of G that maps V(G) onto P and has the same facial cycles and outer face as G. We investigate the conditions under which a point set P admits a k-angulation and find that, for sets containing at least 2k² points, the only obstructions are those that follow from Euler's formula.
Mon, 19 Oct 2020 07:43:49 GMThttp://hdl.handle.net/11420/75922020-10-19T07:43:49Z
- Contractions, removals, and certifying 3-connectivity in line AR timehttp://hdl.handle.net/11420/7640Title: Contractions, removals, and certifying 3-connectivity in line AR time
Authors: Schmidt, Jens M.
Abstract: One of the most noted construction methods of 3-vertex-connected graphs is due to Tutte and is based on the following fact: Any 3-vertex-connected graph G = (V, E) on more than 4 vertices contains a contractible edge, i.e., an edge whose contraction generates a 3-connected graph. This implies the existence of a sequence of edge contractions from G to the complete graph K4, such that every intermediate graph is 3-vertex-connected. A theorem of Barnette and Grünbaum gives a similar sequence using removals on edges instead of contractions. We show how to compute both sequences in optimal time, improving the previously best known running times of O(|V|2) to O(|E|). This result has a number of consequences; an important one is a new linear-time test of 3-connectivity that is certifying; finding such an algorithm has been a major open problem in the design of certifying algorithms in recent years. The test is conceptually different from well-known linear-time 3-connectivity tests and uses a certificate that is easy to verify in time O(|E|). We show how to extend the results to an optimal certifying test of 3-edge-connectivity. © 2013 Society for Industrial and Applied Mathematics.
Thu, 22 Oct 2020 09:20:36 GMThttp://hdl.handle.net/11420/76402020-10-22T09:20:36Z
- Edge-Ordershttp://hdl.handle.net/11420/7603Title: Edge-Orders
Authors: Schlipf, Lena; Schmidt, Jens M.
Abstract: Canonical orderings and their relatives such as st-numberings have been used as a key tool in algorithmic graph theory for the last decades. Recently, a unifying link behind all these orders has been shown that links them to well-known graph decompositions into parts that have a prescribed vertex-connectivity. Despite extensive interest in canonical orderings, no analogue of this unifying concept is known for edge-connectivity. In this paper, we establish such a concept named edge-orders and show how to compute (1, 1)-edge-orders of 2-edge-connected graphs as well as (2, 1)-edge-orders of 3-edge-connected graphs in linear time, respectively. While the former can be seen as the edge-variants of st-numberings, the latter are the edge-variants of Mondshein sequences and non-separating ear decompositions. The methods that we use for obtaining such edge-orders differ considerably in almost all details from the ones used for their vertex-counterparts, as different graph-theoretic constructions are used in the inductive proof and standard reductions from edge- to vertex-connectivity are bound to fail. As a first application, we consider the famous Edge-Independent Spanning Tree Conjecture, which asserts that every k-edge-connected graph contains k rooted spanning trees that are pairwise edge-independent. We illustrate the impact of the above edge-orders by deducing algorithms that construct 2- and 3-edge independent spanning trees of 2- and 3-edge-connected graphs, the latter of which improves the best known running time from O(n 2 ) to linear time.
Mon, 19 Oct 2020 11:26:54 GMThttp://hdl.handle.net/11420/76032020-10-19T11:26:54Z
- On the circumference of essentially 4-connected planar graphshttp://hdl.handle.net/11420/7600Title: On the circumference of essentially 4-connected planar graphs
Authors: Fabrici, Igor; Harant, Jochen; Mohr, Samuel; Schmidt, Jens M.
Abstract: A planar graph is essentially 4-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 essentially 4-connected planar graph G on n vertices contains a cycle of length at least (Formula presented), and this result has recently been improved multiple times. In this paper, we prove that every essentially 4-connected planar graph G on n vertices contains a cycle of length at least (Formula presented) (n+2). This improves the previously best-known lower bound (Formula presented) (n+2).
Mon, 19 Oct 2020 11:17:54 GMThttp://hdl.handle.net/11420/76002020-10-19T11:17:54Z
- Tight bounds for the vertices of degree k in minimally k-connected graphshttp://hdl.handle.net/11420/7609Title: Tight bounds for the vertices of degree k in minimally k-connected graphs
Authors: Schmidt, Jens M.
Abstract: For minimally k-connected graphs on n vertices, Mader proved a tight lower bound for the number |Vk| 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 m : |E| 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.
Mon, 19 Oct 2020 12:16:52 GMThttp://hdl.handle.net/11420/76092020-10-19T12:16:52Z
- Edge-ordershttp://hdl.handle.net/11420/7608Title: Edge-orders
Authors: Schlipf, Lena; Schmidt, Jens M.
Abstract: Canonical orderings and their relatives such as st-numberings have been used as a key tool in algorithmic graph theory for the last decades. Recently, a unifying link behind all these orders has been shown that links them to well-known graph decompositions into parts that have a prescribed vertex-connectivity. Despite extensive interest in canonical orderings, no analogue of this unifying concept is known for edge-connectivity. In this paper, we establish such a concept named edge-orders and show how to compute (1,1)-edge-orders of 2-edge-connected graphs as well as (2,1)-edge-orders of 3-edge-connected graphs in linear time, respectively. While the former can be seen as the edge-variants of st-numberings, the latter are the edge-variants of Mondshein sequences and nonseparating ear decompositions. The methods that we use for obtaining such edge-orders differ considerably in almost all details from the ones used for their vertex-counterparts, as different graph-theoretic constructions are used in the inductive proof and standard reductions from edgeto vertex-connectivity are bound to fail. As a first application, we consider the famous Edge-Independent Spanning Tree Conjecture, which asserts that every k-edge-connected graph contains k rooted spanning trees that are pairwise edge-independent. We illustrate the impact of the above edge-orders by deducing algorithms that construct 2- and 3-edge independent spanning trees of 2- and 3-edge-connected graphs, the latter of which improves the best known running time from O(n2) to linear time.
Mon, 19 Oct 2020 12:14:43 GMThttp://hdl.handle.net/11420/76082020-10-19T12:14:43Z
- Shortness 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:20Z
- Simple computation of st-edge- and st-numberings from ear decompositionshttp://hdl.handle.net/11420/7604Title: Simple computation of st-edge- and st-numberings from ear decompositions
Authors: Schlipf, Lena; Schmidt, Jens M.
Abstract: We propose simple algorithms for computing st-numberings and st-edge-numberings of graphs with running time O(m). Unlike previous serial algorithms, these are not dependent on an initially chosen DFS-tree. Instead, we compute st-(edge-)numberings that are consistent with any open ear decomposition D of a graph in the sense that every ear of D is numbered increasingly or decreasingly. Recent applications need such st-numberings, and the only two linear-time algorithms that are known for this task use a complicated order data structure as black box. We avoid using this data structure by introducing a new and light-weight numbering scheme. In addition, we greatly simplify the recent algorithms for computing (the much less known) st-edge-numberings.
Mon, 19 Oct 2020 11:28:23 GMThttp://hdl.handle.net/11420/76042020-10-19T11:28:23Z
- Computing minimum cycle bases in weighted partial 2-trees in linear timehttp://hdl.handle.net/11420/7633Title: Computing minimum cycle bases in weighted partial 2-trees in linear time
Authors: Doerr, Carola; Ramakrishna, G.; Schmidt, Jens M.
Abstract: We present a linear time algorithm for computing an implicit linear space representation of a minimum cycle basis in weighted partial 2-trees (i.e., graphs of treewidth at most two) with non-negative edge-weights. The implicit representation can be made explicit in a running time that is proportional to the size of the minimum cycle basis. For planar graphs, Borradaile, Sankowski, and Wulff-Nilsen [Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time, FOCS 2010] showed how to compute an implicit O(n log n) space representation of an minimum cycle basis in O(n log5 n) time. For the special case of par-tial 2-trees, our algorithm improves this result to linear time and space. Such an improvement was achieved previously only for outerplanar graphs. [Liu and Lu: Minimum Cycle Bases of Weighted Outerplanar Graphs, IPL 110:970-974, 2010].
Wed, 21 Oct 2020 16:51:02 GMThttp://hdl.handle.net/11420/76332020-10-21T16:51:02Z
- Largest inscribed rectangles in convex polygonshttp://hdl.handle.net/11420/7638Title: Largest inscribed rectangles in convex polygons
Authors: Knauer, Christian; Schlipf, Lena; Schmidt, Jens M.; Tiwary, Hans Raj
Abstract: We consider approximation algorithms for the problem of computing an inscribed rectangle having largest area in a convex polygon on n vertices. If the order of the vertices of the polygon is given, we present a randomized algorithm that computes an inscribed rectangle with area at least (1/ε) times the optimum with probability t in time O(1εlogn) for any constant t<1. We further give a deterministic approximation algorithm that computes an inscribed rectangle of area at least (1-ε) times the optimum in running time O(1 ε2logn) and show how this running time can be slightly improved.
Thu, 22 Oct 2020 08:44:38 GMThttp://hdl.handle.net/11420/76382020-10-22T08:44:38Z
- Construction sequences and certifying 3-connectivityhttp://hdl.handle.net/11420/7591Title: Construction sequences and certifying 3-connectivity
Authors: Schmidt, Jens M.
Abstract: Tutte proved that every 3-vertex-connected graph G on more than 4 vertices has a contractible edge. Barnette and Grünbaum proved the existence of a removable edge in the same setting. We show that the sequence of contractions and the sequence of removals from G to K₄ can be computed in O(|V|²) time by extending Barnette's and Grünbaum's theorem. As an application, we derive a certificate for the 3-vertex-connectivity of graphs that can be easily computed and verified.
Mon, 19 Oct 2020 07:42:48 GMThttp://hdl.handle.net/11420/75912020-10-19T07:42:48Z
- A simple test on 2-vertex- and 2-edge-connectivityhttp://hdl.handle.net/11420/7622Title: A simple test on 2-vertex- and 2-edge-connectivity
Authors: Schmidt, Jens M.
Abstract: 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 are known. Here, an even simpler linear-time algorithm is presented that computes a structure from which both the 2-vertex- and 2-edge-connectivity of a graph can be easily "read off ". The algorithm computes all bridges and cut vertices of the input graph in the same time.
Tue, 20 Oct 2020 12:11:01 GMThttp://hdl.handle.net/11420/76222020-10-20T12:11:01Z
- Computing 2-walks in polynomial timehttp://hdl.handle.net/11420/7590Title: Computing 2-walks in polynomial time
Authors: Schmid, Andreas; Schmidt, Jens M.
Abstract: 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 mentioned above. Its running time is O(n³).
Mon, 19 Oct 2020 07:38:34 GMThttp://hdl.handle.net/11420/75902020-10-19T07:38:34Z
- Cubic plane graphs on a given point sethttp://hdl.handle.net/11420/7632Title: Cubic plane graphs on a given point set
Authors: Schmidt, Jens M.; Valtr, Pavel
Abstract: Let P be a set of n ≥ 4 points in the plane that is in general position and such that n is even. We investigate the problem whether there is a cubic plane straight-line graph on P. No polynomial-time algorithm is known for this problem. Based on a reduction to the existence of certain diagonals of the boundary cycle of the convex hull of P, we give the first polynomial-time algorithm; the algorithm is constructive and runs in time O(n 3). We also show which graph structure can be expected when there is a cubic plane graph on P; e. g., if P admits a 2-connected cubic plane graph, we show that P admits also a 2-connected cubic plane graph that contains the boundary cycle of P. The algorithm extends to checking P on admitting a 2-connected cubic plane graph.
Wed, 21 Oct 2020 16:44:43 GMThttp://hdl.handle.net/11420/76322020-10-21T16:44:43Z
- Construction sequences and certifying 3-connectednesshttp://hdl.handle.net/11420/7652Title: Construction sequences and certifying 3-connectedness
Authors: Schmidt, Jens M.
Abstract: Tutte proved that every 3-connected graph on more than 4 nodes has a contractible edge. Barnette and Grünbaum proved the existence of a removable edge in the same setting. We show that the sequence of contractions and the sequence of removals from G to the K4 can be computed in O(|V|2) time by extending Barnette and Grünbaum's theorem. As an application, we derive a certificate for the 3-connectedness of graphs that can be easily computed and verified.
Fri, 23 Oct 2020 10:50:52 GMThttp://hdl.handle.net/11420/76522020-10-23T10:50:52Z
- Linear-time recognition of map graphs with outerplanar witnesshttp://hdl.handle.net/11420/4533Title: Linear-time recognition of map graphs with outerplanar witness
Authors: Mnich, Matthias; Rutter, Ignaz; Schmidt, Jens M.
Abstract: Map graphs generalize planar graphs and were introduced by Chen et al. (STOC 1998, J. ACM, 2002). They showed that the problem of recognizing map graphs is in by proving the existence of a planar witness graph . Shortly after, Thorup (FOCS 1998) published a polynomial-time recognition algorithm for map graphs. However, the run time of this algorithm is estimated to be for
-vertex graphs, and a full description of its details remains unpublished.
We give a new and purely combinatorial algorithm that decides whether a graph
is a map graph having an outerplanar witness . This is a step towards a first combinatorial recognition algorithm for general map graphs. The algorithm runs in time and space . In contrast to Thorup’s approach, it computes the witness graph in the affirmative case.
Fri, 24 Jan 2020 09:38:34 GMThttp://hdl.handle.net/11420/45332020-01-24T09:38:34Z
- Thoughts on Barnette's conjecturehttp://hdl.handle.net/11420/7620Title: Thoughts on Barnette's conjecture
Authors: Alt, Helmut; Payne, Michael Stuart; Schmidt, Jens M.; Wood, David R.
Abstract: We prove a new sufficient condition for a cubic 3-connected planar graph to be Hamiltonian. This condition is most easily described as a property of the dual graph. Let G be a planar triangulation. Then the dual G* is a cubic 3-connected planar graph, and G* is bipartite if and only if G is Eulerian. We prove that if the vertices of G are (improperly) coloured blue and red, such that the blue vertices cover the faces of G, there is no blue cycle, and every red cycle contains a vertex of degree at most 4, then G* is Hamiltonian.
This result implies the following special case of Barnette's Conjecture: if G is an Eulerian planar triangulation, whose vertices are properly coloured blue, red and green, such that every red-green cycle contains a vertex of degree 4, then G* is Hamiltonian. Our final result highlights the limitations of using a proper colouring of G as a starting point for proving Barnette's Conjecture. We also explain related results on Barnette's Conjecture that were obtained by Kelmans and for which detailed self-contained proofs have not been published.
Tue, 20 Oct 2020 12:01:18 GMThttp://hdl.handle.net/11420/76202020-10-20T12:01:18Z
- Effiziente Extraktion von Kuratowski-Teilgraphenhttp://hdl.handle.net/11420/7598Title: Effiziente Extraktion von Kuratowski-Teilgraphen
Authors: Schmidt, Jens M.
Abstract: Ein Graph ist nach dem Satz von Kuratowski genau dann planar, wenn er keine Kuratowski-Subdivisions enth\"alt. Eine einzelne davon kann von modernen Planarit\"atstests bei nicht planaren Eingabegraphen in Linearzeit extrahiert werden. Allerdings existieren Anwendungen, die nicht nur eine, sondern m\"oglichst viele dieser Kuratowski-Subdivisions ben\"otigen. Dazu geh\"oren Branch-and-Cut-Algorithmen f\"ur einige NP-schwere Probleme, wie beispielsweise die Kreuzungsminimierung oder auch verschiedene Varianten des Maximum Planar Subgraph Problems. Die Kuratowski-Subdivisions erm\"oglichen dort die Berechnung von zus\"atzlichen nebenbedingungen einer LP-Relaxierung. Dabei ist es w\"unschenswert, dass die Kuratowski-Subdivisions paarweise entweder
m\"oglichst viele Kanten gemeinsam haben oder weitgehend kantendisjunkt sind.
In dieser Diplomarbeit wird ein Algorithmus entworfen und analysiert, der mehrere Kuratowski-Subdivisions in linearer Zeit O(n + m + Sum_(K in S) |E(K)|) extrahieren kann, wobei S die Menge der gefundenen Kuratowski-Subdivisions ist. Dieser Algorithmus stellt eine Erweiterung des aktuellen Planarit\"atstests von Boyer und Myrvold dar und kann zus\"atzlich so modifiziert werden, dass entweder m\"oglichst \"ahnliche oder m\"oglichst verschiedene Kuratowski-Subdivisions ausgegeben werden. Die Laufzeit des Algorithmus ist dabei asymptotisch optimal. Aus diesem Algorithmus wird ein zweiter Ansatz entwickelt, der in der Praxis mehr Kuratowski-Subdivisions extrahieren kann, daf\"ur aber zu einer superlinearen Laufzeit f\"uhrt. Beide Verfahren werden implementiert und deren Praxistauglichkeit verglichen.
Mon, 19 Oct 2020 09:37:06 GMThttp://hdl.handle.net/11420/75982020-10-19T09:37:06Z
- High-order punishment and the evolution of cooperationhttp://hdl.handle.net/11420/7636Title: High-order punishment and the evolution of cooperation
Authors: Baranski, Bastian; Schmitt, Karlheinz; Seis, Danny; Slodzinski, Rafael; Steeg, Simon; Wiemann, Nils; Zimmermann, Marc; Bartz-Beielstein, Thomas; Ehlers, Rüdiger; Kajendran, Thusinthan; Kosslers, Björn; Mehnen, Jörn; Polaszek, Tomasz; Reimholz, Ralf; Schmidt, Jens M.
Abstract: The Prisoner's Dilemma and the Public Goods Game are models to study mechanisms leading to the evolution of cooperation. From a simplified rational and egoistic perspective there should be no altruistic cooperation in these games at all. Previous studies observed circumstances under which cooperation can emerge. This paper demonstrates that high-order punishment opportunities can maintain a higher cooperation level in an agent based simulation of the evolution of cooperation.
Thu, 22 Oct 2020 08:34:55 GMThttp://hdl.handle.net/11420/76362020-10-22T08:34:55Z
- Structure and constructions of 3-connected graphshttp://hdl.handle.net/11420/7597Title: Structure and constructions of 3-connected graphs
Authors: Schmidt, Jens M.
Abstract: The class of 3-connected (i.e. 3-vertex-connected) graphs has been studied intensively for many reasons in the past 50 years. One algorithmic reason is that graph problems can often be reduced to handle only 3-connected graphs; applications include problems in graph drawing, problems related to planarity and online problems on planar graphs. It is possible to test a graph on being 3-connected in linear time. However, the linear-time algorithms known are complicated and difficult to implement. For that reason, it is essential to check implementations of these algorithms to be correct. A way to check the correctness of an algorithm for every instance is to make it certifying, i. e., to enhance its output by an easy-to-verify certificate of correctness for that output. However, surprisingly few work has been devoted to find certifying algorithms that test 3-connectivity; in fact, the currently fastest algorithms need quadratic time.
Two classic results in graph theory due to Barnette, Gr\"unbaum and Tutte show that 3-connected graphs can be characterized by the existence of certain inductively defined constructions. We give new variants of these constructions, relate these to already existing ones and show how they can be exploited algorithmically. Our main result is a linear-time certifying algorithm for testing 3-connectivity, which
is based on these constructions. This yields also simple certifying algorithms in linear time for 2-connectivity, 2-edge-connectivity and 3-edge-connectivity. We conclude this thesis by a structural result that shows that one of the constructions is preserved when being applied to depth-first trees of the graph only.
Mon, 19 Oct 2020 09:29:02 GMThttp://hdl.handle.net/11420/75972020-10-19T09:29:02Z
- Computing vertex-disjoint paths in large graphs using MAOShttp://hdl.handle.net/11420/7606Title: Computing vertex-disjoint paths in large graphs using MAOS
Authors: Preißer, Johanna E.; Schmidt, Jens M.
Abstract: We consider the problem of computing k ∈ N internally vertex-disjoint paths between special vertex pairs of simple connected graphs. For general vertex pairs, the best deterministic time bound is, since 42 years, O(min{k, n}m) for each pair by using traditional flow-based methods. The restriction of our vertex pairs comes from the machinery of maximal adjacency orderings (MAOs). Henzinger showed for every MAO and every 1 ≤ k ≤ δ (where δ is the minimum degree of the graph) the existence of k internally vertex-disjoint paths between every pair of the last δ − k + 2 vertices of this MAO. Later, Nagamochi generalized this result by using the machinery of mixed connectivity. Both results are however inherently non-constructive. We present the first algorithm that computes these k internally vertex-disjoint paths in linear time O(m), which improves the previously best time O(min{k, n}m). Due to the linear running time, this algorithm is suitable for large graphs. The algorithm is simple, works directly on the MAO structure, and completes a long history of purely existential proofs with a constructive method. We extend our algorithm to compute several other path systems and discuss its impact for certifying algorithms.
Mon, 19 Oct 2020 11:51:31 GMThttp://hdl.handle.net/11420/76062020-10-19T11:51:31Z
- Computing tutte pathshttp://hdl.handle.net/11420/7593Title: Computing tutte paths
Authors: Schmid, Andreas; Schmidt, Jens M.
Abstract: Tutte paths are one of the most successful tools for attacking problems on long cycles in planar graphs. Unfortunately, results based on them are non-constructive, as their proofs inherently use an induction on overlapping subgraphs and these overlaps prevent any attempt to bound the running time by 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 [5] showed how to compute such paths in linear time. For 3-connected planar graphs, Tutte paths have a significantly more complicated structure, and it has only recently been shown that they can be computed in polynomial time [24]. However, Tutte paths are defined for general 2-connected planar graphs and this is what most applications need. In this unrestricted setting, no computational results for Tutte paths are known. We give the first e cient algorithm that computes a Tutte path (in this unrestricted setting). One of the strongest existence results about such Tutte paths is due to Sanders [23], which allows one 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 such a special Tutte path e ciently. Our method refines both, the existence results of Thomassen [29] and Sanders [23], and avoids that the subgraphs arising in the inductive proof intersect in more than one edge by using a novel iterative decomposition along 2-separators. Finally, we show that our algorithm runs in time O(n2).
Mon, 19 Oct 2020 07:46:06 GMThttp://hdl.handle.net/11420/75932020-10-19T07:46:06Z
- A 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
- Lower bounds for locally highly connected graphshttp://hdl.handle.net/11420/4551Title: Lower bounds for locally highly connected graphs
Authors: Adamaszek, Anna; Adamaszek, Michal; Mnich, Matthias; Schmidt, Jens M.
Abstract: We propose a conjecture regarding the lower bound for the number of edges in locally k-connected graphs and we prove it for \(k=2\). In particular, we show that every connected locally 2-connected graph is \(M_3\)-rigid. For the special case of surface triangulations, this fact was known before using topological methods. We generalize this result to all locally 2-connected graphs and give a purely combinatorial proof. Our motivation to study locally k-connected graphs comes from lower bound conjectures for flag triangulations of manifolds, and we discuss some more specific problems in this direction.
Fri, 24 Jan 2020 11:01:00 GMThttp://hdl.handle.net/11420/45512020-01-24T11:01:00Z
- Small-area orthogonal drawings of 3-connected graphshttp://hdl.handle.net/11420/7615Title: Small-area orthogonal drawings of 3-connected graphs
Authors: Biedl, Therese; Schmidt, Jens M.
Abstract: It is well-known that every graph with maximum degree 4 has an orthogonal drawing with area at most 49/64 n2+O(n)≈0.76n2. In this paper, we show that if the graph is 3-connected, then the area can be reduced even further to9/16n2+O(n)≈0.56n2.Thedrawingusesthe 3-canonical order for (not necessarily planar) 3-connected graphs, which is a special Mondshein sequence and can hence be computed in linear time. To our knowledge, this is the first application of a Mondshein sequence in graph drawing.
Mon, 19 Oct 2020 13:09:11 GMThttp://hdl.handle.net/11420/76152020-10-19T13:09:11Z
- The Mondshein sequencehttp://hdl.handle.net/11420/7613Title: The Mondshein sequence
Authors: Schmidt, Jens M.
Abstract: 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 generalization of canonical orderings to non-planar graphs that was published by Lee Mondshein in a PhD-thesis at M.I.T. as early as 1971. Mondshein proposed to order the vertices of a graph in a sequence such that, for any i, the vertices from 1 to i induce essentially a 2-connected graph while the remaining vertices from i + 1 to n induce a connected graph. Mondshein's sequence generalizes canonical orderings and became later and independently known under the name non-separating ear decomposition. Currently, the best known algorithm for computing this sequence achieves a running time of O(nm); the main open problem in Mondshein's and follow-up work is to improve this running time to a subquadratic time. In this paper, we present the first algorithm that computes a Mondshein sequence in time and space O(m), improving the previous best running time by a factor of n. In addition, we illustrate the impact of this result by deducing linear-time algorithms for several other problems, for which the previous best running times have been quadratic. In particular, we show how to compute three independent spanning trees in a 3-connected graph in linear time, improving a result of Cheriyan and Maheshwari [J. Algorithms 9(4)]. Secondly, we improve the preprocessing time for the output-sensitive data structure by Di Battista, Tamassia and Vismara [Algorithmica 23(4)] that reports three internally disjoint paths between any given vertex pair from O(n2) to O(m). Thirdly, we improve the computation of 3-partitioning of a 3-connected graph to linear time. Finally, we show how a very simple linear-time planarity test can be derived once a Mondshein sequence is computed.
Mon, 19 Oct 2020 12:53:12 GMThttp://hdl.handle.net/11420/76132020-10-19T12:53:12Z
- Efficient extraction of multiple Kuratowski subdivisionshttp://hdl.handle.net/11420/7596Title: Efficient extraction of multiple Kuratowski subdivisions
Authors: Chimani, Markus; Mutzel, Petra; Schmidt, Jens M.
Abstract: A graph is planar if and only if it does not contain a Kuratowski subdivision. Hence such a subdivision can be used as a witness for non-planarity. Modern planarity testing algorithms allow to extract a single such witness in linear time. We present the first linear time algorithm which is able to extract multiple Kuratowski subdivisions at once. This is of particular interest for, e.g., Branch-and-Cut algorithms which require multiple such subdivisions to generate cut constraints. The algorithm is not only described theoretically, but we also present an experimental study of its implementation.
Mon, 19 Oct 2020 07:54:08 GMThttp://hdl.handle.net/11420/75962020-10-19T07:54:08Z
- Interval stabbing problems in small integer rangeshttp://hdl.handle.net/11420/7651Title: Interval stabbing problems in small integer ranges
Authors: Schmidt, Jens M.
Abstract: Given a set I of n intervals, a stabbing query consists of a point q and asks for all intervals in I that contain q. The Interval Stabbing Problem is to find a data structure that can handle stabbing queries efficiently. We propose a new, simple and optimal approach for different kinds of interval stabbing problems in a static setting where the query points and interval ends are in 1,⋯,O(n). © 2009 Springer-Verlag Berlin Heidelberg.
Fri, 23 Oct 2020 10:49:07 GMThttp://hdl.handle.net/11420/76512020-10-23T10:49:07Z
- Computing minimum cycle bases in weighted partial 2-trees in linear timehttp://hdl.handle.net/11420/7634Title: Computing minimum cycle bases in weighted partial 2-trees in linear time
Authors: Doerr, Carola; Ramakrishna, G.; Schmidt, Jens M.
Abstract: We present a linear time algorithm for computing an implicit linear space representation of a minimum cycle basis (MCB) in weighted partial 2-trees, i.e., graphs of treewidth two. The implicit representation can be made explicit in a running time that is proportional to the size of the MCB. For planar graphs, Borradaile, Sankowski, and Wulff-Nilsen [Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time, FOCS 2010] showed how to compute an implicit O(n logn) space representation of an MCB in O(n log5 n) time. For the special case of partial 2-trees, our algorithm improves this result to linear time and space. Such an improvement was achieved previously only for outerplanar graphs [Liu and Lu: Minimum Cycle Bases of Weighted Outerplanar Graphs, IPL 110:970-974, 2010].
Wed, 21 Oct 2020 16:55:17 GMThttp://hdl.handle.net/11420/76342020-10-21T16:55:17Z
- Certifying 3-connectivity in linear timehttp://hdl.handle.net/11420/7653Title: Certifying 3-connectivity in linear time
Authors: Schmidt, Jens M.
Abstract: One of the most noted construction methods of 3-vertex-connected graphs is due to Tutte and based on the following fact: Every 3-vertex-connected graph G on more than 4 vertices contains a contractible edge, i. e., an edge whose contraction generates a 3-connected graph. This implies the existence of a sequence of edge contractions from G to K 4 such that every intermediate graph is 3-vertex-connected. A theorem of Barnette and Grünbaum yields a similar sequence using removals of edges instead of contractions. We show how to compute both sequences in optimal time, improving the previously best known running times of O(|V|2) to O(|E|). Based on this result, we give a linear-time test of 3-connectivity that is certifying; finding such an algorithm has been a major open problem in the design of certifying algorithms in the last years. The 3-connectivity test is conceptually different from well-known linear-time tests of 3-connectivity; it uses a certificate that is easy to verify in time O(|E|). We also provide an optimal certifying test of 3-edge-connectivity.
Fri, 23 Oct 2020 10:52:25 GMThttp://hdl.handle.net/11420/76532020-10-23T10:52:25Z
- A planarity test via construction sequenceshttp://hdl.handle.net/11420/7654Title: A planarity test via construction sequences
Authors: Schmidt, Jens M.
Abstract: 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 to give simpler linear-time tests. We give a conceptually simple reduction from planarity testing to the problem of computing a certain construction of a 3-connected graph. This implies a linear-time planarity test. Our approach is radically different from all previous linear-time planarity tests; as key concept, we maintain a planar embedding that is 3-connected at each point in time. The algorithm computes a planar embedding if the input graph is planar and a Kuratowski-subdivision otherwise.
Fri, 23 Oct 2020 10:53:49 GMThttp://hdl.handle.net/11420/76542020-10-23T10:53:49Z
- Certifying 3-edge-connectivityhttp://hdl.handle.net/11420/7655Title: Certifying 3-edge-connectivity
Authors: Mehlhorn, Kurt; Neumann, Adrian; Schmidt, Jens M.
Abstract: We present a linear-time certifying algorithm that tests graphs for 3-edge-connectivity. If the input graph G is not 3-edge-connected, the algorithm returns a 2-edge-cut. If G is 3-edge-connected, the algorithm returns a construction sequence that constructs G from the graph with two nodes and three parallel edges using only operations that (obviously) preserve 3-edge-connectivity.
Fri, 23 Oct 2020 15:18:31 GMThttp://hdl.handle.net/11420/76552020-10-23T15:18:31Z
- The impact of group reputation in multiagent environmentshttp://hdl.handle.net/11420/7635Title: The impact of group reputation in multiagent environments
Authors: Baranski, Bastian; Bartz-Beielstein, Thomas; Ehlers, Rüdiger; Kajendran, Thusinthan; Kosslers, Björn; Mehnen, Jörn; Polaszek, Tomasz; Reimholz, Ralf; Schmidt, Jens M.; Schmitt, Karlheinz; Seis, Danny; Slodzinski, Rafael; Steeg, Simon; Wiemann, Nils; Zimmermann, Marc
Abstract: This paper presents results from extensive simulation studies on the iterated prisoner's dilemma. Two models were implemented: a nongroup model in order to study fundamental principles of cooperation and a model to imitate ethnocentrism. Some extensions of Axelrod's elementary model implemented individual reputation. We furthermore introduced group reputation to provide a more realistic scenario. In an environment with group reputation the behavior of one agent will affect the reputation of the whole group and vice-versa. While kind agents (e. g. those with a cooperative behavior) lose reputation when being in a group, in which defective strategies are more common, agents with defective behavior on the other hand benefit from a group with more cooperative strategies. We demonstrate that group reputation decreases cooperation with the in-group and increases cooperation with the out-group.
Wed, 21 Oct 2020 17:01:40 GMThttp://hdl.handle.net/11420/76352020-10-21T17:01:40Z
- Computing vertex-disjoint paths in large graphs using MAOshttp://hdl.handle.net/11420/7602Title: Computing vertex-disjoint paths in large graphs using MAOs
Authors: Preißer, Johanna E.; Schmidt, Jens M.
Abstract: We consider the problem of computing k∈ N internally vertex-disjoint paths between special vertex pairs of simple connected graphs. For general vertex pairs, the best deterministic time bound is, since 42 years, O(min{k,n}m) for each pair by using traditional flow-based methods. The restriction of our vertex pairs comes from the machinery of maximal adjacency orderings (MAOs). Henzinger showed for every MAO and every 1 ≤ k≤ δ (where δ is the minimum degree of the graph) the existence of k internally vertex-disjoint paths between every pair of the last δ- k+ 2 vertices of this MAO. Later, Nagamochi generalized this result by using the machinery of mixed connectivity. Both results are however inherently non-constructive. We present the first algorithm that computes these k internally vertex-disjoint paths in linear time O(n+ m) , which improves the previously best time O(min{k,n}m). Due to the linear running time, this algorithm is suitable for large graphs. The algorithm is simple, works directly on the MAO structure, and completes a long history of purely existential proofs with a constructive method. We extend our algorithm to compute several other path systems and discuss its impact for certifying algorithms.
Mon, 19 Oct 2020 11:22:57 GMThttp://hdl.handle.net/11420/76022020-10-19T11:22:57Z
- Longer cycles in essentially 4-Connected planar graphshttp://hdl.handle.net/11420/7595Title: Longer cycles in essentially 4-Connected planar graphs
Authors: Fabrici, Igor; Harant, Jochen; Mohr, Samuel; Schmidt, Jens M.
Abstract: A planar 3-connected graph G is called essentially 4-connected if, for every 3-separator S, at least one of the two components of G-S is an isolated vertex. Jackson and Wormald proved that the length circ(G) of a longest cycle of any essentially 4-connected planar graph G on n vertices is at least (2n+4/5) and Fabrici, Harant and Jendrol' improved this result to circ(G)≥ ½(n+4). In the present paper, we prove that an essentially 4-connected planar graph on n vertices contains a cycle of length at least ⅗(n+2) and that such a cycle can be found in time O(n²).
Mon, 19 Oct 2020 07:51:37 GMThttp://hdl.handle.net/11420/75952020-10-19T07:51:37Z
- Certifying 3-edge-connectivityhttp://hdl.handle.net/11420/7607Title: Certifying 3-edge-connectivity
Authors: Mehlhorn, Kurt; Neumann, Adrian; Schmidt, Jens M.
Abstract: 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 2-edge-cut. If it is 3-edge-connected, it returns a construction sequence that constructs the input graph from the graph with two vertices and three parallel edges using only operations that (obviously) preserve 3-edge-connectivity. Additionally, we show how to compute and certify the 3-edge-connected components and a cactus representation of the 2-cuts in linear time. For 3-vertex-connectivity, we show how to compute the 3-vertex-connected components of a 2-connected graph.
Mon, 19 Oct 2020 12:10:27 GMThttp://hdl.handle.net/11420/76072020-10-19T12:10:27Z
- Longest 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:35Z
- Compact 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:55Z
- On short fastest paths in temporal graphshttp://hdl.handle.net/11420/8390Title: On short fastest paths in temporal graphs
Authors: Danda, Umesh Sandeep; Ramakrishna, G.; Schmidt, Jens M.; Srikanth, M.
Tue, 12 Jan 2021 17:15:33 GMThttp://hdl.handle.net/11420/83902021-01-12T17:15:33Z
- Cycle spectra of contraction-critically 4-connected planar graphshttp://hdl.handle.net/11420/9863Title: Cycle spectra of contraction-critically 4-connected planar graphs
Authors: Lo, On-Hei Solomon; Schmidt, Jens M.
Abstract: Motivated by the long-standing and wide open pancyclicity conjectures of Bondy and Malkevitch, we study the cycle spectra of contraction-critically 4-connected planar graphs. We show that every contraction-critically 4-connected planar graph on n vertices contains a cycle of length k for every k∈⌊n2⌋-⌈n108⌉,⋯,⌊n2⌋+⌊n36⌋∪23n,⋯,n.
Mon, 12 Jul 2021 06:16:44 GMThttp://hdl.handle.net/11420/98632021-07-12T06:16:44Z
- Circumference of essentially 4-connected planar triangulationshttp://hdl.handle.net/11420/8419Title: Circumference of essentially 4-connected planar triangulations
Authors: Fabrici, Igor; Harant, Jochen; Mohr, Samuel; Schmidt, Jens M.
Wed, 13 Jan 2021 15:23:29 GMThttp://hdl.handle.net/11420/84192021-01-13T15:23:29Z