O.H. S. Lo, J. M. Schmidt and M. Thorup. Compact Cactus Representations of all NonTrivial MinCuts. Discrete Applied Mathematics, to appear.  
Abstract: Recently, Kawarabayashi and Thorup presented the first deterministic edgeconnectivity recognition algorithm in nearlinear 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 $O(n/$ vertices and $O(n)$ edges that preserves all nontrivial mincuts of $G$, where $ is the minimum degree of $G$ and $O$ hides logarithmic factors. We present a simple argument that improves this contractionbased sparsifier by eliminating the polylogarithmic factors, that is, we show a contractionbased sparsification that leaves $O(n/$ vertices and $O(n)$ edges, preserves all nontrivial mincuts and can be computed in nearlinear time $O(m)$, where $m$ is the number of edges of $G$. We also obtain that every simple graph has $O((n/^2)$ nontrivial mincuts. Our approach allows to represent all nontrivial mincuts 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 mincuts in linear time. We apply this compact structure to show that all mincuts can be explicitly listed in $O(m) + O(n^2 / $ time for every simple graph, which improves the previous best time bound $O(nm)$ given by Gusfield and Naor. 

@article{Lo2020a, author = {O.H. S. Lo and J. M. Schmidt and M. Thorup}, title = {Compact Cactus Representations of all NonTrivial MinCuts}, journal = {Discrete Applied Mathematics}, year = {to appear} }  
I. Fabrici, J. Harant, S. Mohr and J. M. Schmidt. Longer Cycles in Essentially 4Connected Planar Graphs. Discussiones Mathematicae Graph Theory, 40:269277, 2020.  
Abstract: A planar 3connected graph G is called essentially 4connected if, for every 3separator S, at least one of the two components of GS is an isolated vertex. Jackson and Wormald proved that the length circ(G) of a longest cycle of any essentially 4connected 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)/2. In the present paper, we prove that an essentially 4connected planar graph on n vertices contains a cycle of length at least 3(n+2)/5 and that such a cycle can be found in time O(n^2). 

@article{Fabrici2020, author = {I. Fabrici and J. Harant and S. Mohr and J. M. Schmidt}, title = {Longer Cycles in Essentially 4Connected Planar Graphs}, journal = {Discussiones Mathematicae Graph Theory}, year = {2020}, volume = {40}, pages = {269277}, doi = {http://dx.doi.org/10.7151/dmgt.2133} }  
I. Fabrici, J. Harant, S. Mohr and J. M. Schmidt. On the Circumference of Essentially 4connected Planar Graphs. Journal of Graph Algorithms and Applications, 24(1):2146, 2020.  
Abstract: A planar graph is essentially $4$connected if it is 3connected and every of its 3separators is the neighborhood of a single vertex. Jackson and Wormald proved that every essentially 4connected planar graph $G$ on $n$ vertices contains a cycle of length at least $2n+45$, and this result has recently been improved multiple times. In this paper, we prove that every essentially 4connected planar graph $G$ on $n$ vertices contains a cycle of length at least $58(n+2)$. This improves the previously bestknown lower bound $35(n+2)$. 

@article{Fabrici2020a, author = {I. Fabrici and J. Harant and S. Mohr and J. M. Schmidt}, title = {On the Circumference of Essentially 4connected Planar Graphs}, journal = {Journal of Graph Algorithms and Applications}, year = {2020}, volume = {24}, number = {1}, pages = {2146}, doi = {http://dx.doi.org/10.7155/jgaa.00516} }  
O.H. S. Lo, J. M. Schmidt, N. Van Cleemput and C. T. Zamfirescu. Shortness Coefficient of Cyclically 4EdgeConnected Cubic Graphs. Electronic Journal of Combinatorics, 27(1):P1.43, 114, 2020.  
Abstract: Grünbaum and Malkevitch proved that the shortness coefficient of cyclically 4edgeconnected cubic planar graphs is at most $7677$. Recently, this was improved to $359366 (< 5253)$ and the question was raised whether this can be strengthened to $4142$, a natural bound inferred from one of the FaulknerYounger graphs. We prove that the shortness coefficient of cyclically 4edgeconnected cubic planar graphs is at most $3738$ and that we also get the same value for cyclically 4edgeconnected cubic graphs of genus~g for any prescribed genus g ge 0. We also show that $4546$ is an upper bound for the shortness coefficient of cyclically 4edgeconnected cubic graphs of genus~g with face lengths bounded above by some constant larger than 22 for any prescribed $g ge 0$.  
@article{Lo2020, author = {O.H. S. Lo and J. M. Schmidt and N. {Van C}leemput and C. T. Zamfirescu}, title = {Shortness Coefficient of Cyclically 4EdgeConnected Cubic Graphs}, journal = {Electronic Journal of Combinatorics}, year = {2020}, volume = {27}, number = {1}, pages = {P1.43, 114}, doi = {http://dx.doi.org/10.37236/8440} }  
J. E. Preißer and J. M. Schmidt. Computing VertexDisjoint Paths in Large Graphs using MAOs. Algorithmica, 82(1):146162, 2020.  
Abstract: We consider the problem of computing $k in N$ internally vertexdisjoint paths between special vertex pairs of simple connected graphs. For general vertex pairs, the best deterministic time bound is since 42 years $O(mink,nm)$ for each pair by using traditional flowbased methods. The restriction of our vertex pairs comes from the machinery of maximal adjacency orderings (MAOs). Henzinger showed for every MAO and every $1 leq k leq (where $ is the minimum degree of the graph) the existence of $k$ internally vertexdisjoint 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 nonconstructive. We present the first algorithm that computes these $k$ internally vertexdisjoint paths in linear time $O(m)$, which improves the previously best time $O(mink,nm)$. 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. 

@article{Preisser2020, author = {J. E. Prei{\ss}er and J. M. Schmidt}, title = {Computing VertexDisjoint Paths in Large Graphs using {MAO}s}, journal = {Algorithmica}, year = {2020}, volume = {82}, number = {1}, pages = {146162}, doi = {http://dx.doi.org/10.1007/s00453019006082} }  
L. Schlipf and J. M. Schmidt. EdgeOrders. Algorithmica, 81(5):18811900, 2019.  
Abstract: Canonical orderings and their relatives such as stnumberings 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 wellknown graph decompositions into parts that have a prescribed vertexconnectivity. Despite extensive interest in canonical orderings, no analogue of this unifying concept is known for edgeconnectivity. In this paper, we establish such a concept named edgeorders and show how to compute (1,1)edgeorders of 2edgeconnected graphs as well as (2,1)edgeorders of 3edgeconnected graphs in linear time, respectively. While the former can be seen as the edgevariants of stnumberings, the latter are the edgevariants of Mondshein sequences and nonseparating ear decompositions. The methods that we use for obtaining such edgeorders differ considerably in almost all details from the ones used for their vertexcounterparts, as different graphtheoretic constructions are used in the inductive proof and standard reductions from edge to vertexconnectivity are bound to fail. As a first application, we consider the famous EdgeIndependent Spanning Tree Conjecture, which asserts that every $k$edgeconnected graph contains $k$ rooted spanning trees that are pairwise edgeindependent. We illustrate the impact of the above edgeorders by deducing algorithms that construct 2 and 3edge independent spanning trees of 2 and 3edgeconnected graphs, the latter of which improves the best known running time from $O(n^2)$ to linear time. 

@article{Schlipf2018, author = {L. Schlipf and J. M. Schmidt}, title = {EdgeOrders}, journal = {Algorithmica}, year = {2019}, volume = {81}, number = {5}, pages = {18811900}, doi = {http://dx.doi.org/10.1007/s0045301805164} }  
L. Schlipf and J. M. Schmidt. Simple Computation of stEdge and stNumberings from Ear Decompositions. Information Processing Letters, 145:5863, 2019.  
Abstract: We propose simple algorithms for computing $st$numberings and $st$edgenumberings of graphs with running time $O(m)$. Unlike previous serial algorithms, these are not dependent on an initially chosen DFStree. 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 lineartime 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 lightweight numbering scheme. In addition, we greatly simplify the recent algorithms for computing (the much less known) $st$edgenumberings. 

@article{Schlipf2019, author = {Lena Schlipf and J. M. Schmidt}, title = {Simple Computation of {st}Edge and {st}Numberings from Ear Decompositions}, journal = {Information Processing Letters}, year = {2019}, volume = {145}, pages = {5863}, doi = {https://doi.org/10.1016/j.ipl.2019.01.008} }  
M. Kriesell and J. M. Schmidt. More on foxes. Journal of Graph Theory, 89(2):101114, 2018.  
Abstract: An edge in a kconnected graph G is called kcontractible if the graph G/e obtained from G by contracting e is kconnected. Generalizing earlier results on 3contractible edges in spanning trees of 3connected graphs, we prove that (except for the graphs K_k+1 for k=1 and k) (a) every spanning tree of a kconnected triangle free graph has two kcontractible edges, We also discuss in which sense these theorems are best possible. 

@article{Kriesell2018, author = {M. Kriesell and J. M. Schmidt}, title = {More on foxes}, journal = {Journal of Graph Theory}, year = {2018}, volume = {89}, number = {2}, pages = {101114}, doi = {http://dx.doi.org/10.1002/jgt.22243} }  
O.H. S. Lo and J. M. Schmidt. Longest Cycles in Cyclically 4EdgeConnected Cubic Planar Graphs. Australasian Journal of Combinatorics, 72(1):155162, 2018.  
Abstract: Grünbaum and Malkevitch proved in 1976 that the shortness coefficient of cyclically 4edgeconnected cubic planar graphs is at most 76/77. We prove that it is at most 359/366 (< 52/53).  
@article{Lo2018, author = {O.H. S. Lo and J. M. Schmidt}, title = {Longest Cycles in Cyclically 4EdgeConnected Cubic Planar Graphs}, journal = {Australasian Journal of Combinatorics}, year = {2018}, volume = {72}, number = {1}, pages = {155162}, url = {http://ajc.maths.uq.edu.au/pdf/72/ajc_v72_p155.pdf} }  
O.H. S. Lo and J. M. Schmidt. A Cut Tree Representation for Pendant Pairs. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC'18), pages 38:138:9, 2018.  
Abstract: Two vertices $v$ and $w$ of a graph $G$ are called a pendant pair if the maximal number of edgedisjoint 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 $)$ pendant pairs; this is the best bound known so far. We improve this result by showing that every simple graph $G$ with minimum degree $delta geq 5$ or with edgeconnectivity $lambda geq 4$ or with vertexconnectivity $kappa geq 3$ contains in fact $delta V)$ pendant pairs. We prove that this bound is tight from several perspectives, and that $delta V)$ pendant pairs can be computed efficiently, namely in linear time when a GomoryHu tree is given. Our method utilizes a new cut tree representation of graphs. 

@inproceedings{Lo2018a, author = {O.H. S. Lo and J. M. Schmidt}, title = {A Cut Tree Representation for Pendant Pairs}, booktitle = {Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC'18)}, year = {2018}, series_ = {Leibniz International Proceedings in Informatics (LIPIcs)}, volume_ = {123}, pages = {38:138:9}, doi = {http://dx.doi.org/10.4230/LIPIcs.ISAAC.2018.38} }  
M. Mnich, I. Rutter and J. M. Schmidt. LinearTime Recognition of Map Graphs with Outerplanar Witness. Discrete Optimization, 28:6377, 2018.  
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 polynomialtime recognition algorithm for map graphs. However, the run time of this algorithm is estimated to be n^120) for nvertex 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. 

@article{Mnich2018, author = {M. Mnich and I. Rutter and J. M. Schmidt}, title = {LinearTime Recognition of Map Graphs with Outerplanar Witness}, journal = {Discrete Optimization}, year = {2018}, volume = {28}, pages = {6377}, doi = {http://dx.doi.org/10.1016/j.disopt.2017.12.002} }  
J. E. Preißer and J. M. Schmidt. Computing VertexDisjoint Paths in Large Graphs using MAOs. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC'18), pages 13:113:12, 2018.  
Abstract: We consider the problem of computing $k in N$ internally vertexdisjoint paths between special vertex pairs of simple connected graphs. For general vertex pairs, the best deterministic time bound is, since 42 years, $O(mink,nm)$ for each pair by using traditional flowbased methods. The restriction of our vertex pairs comes from the machinery of maximal adjacency orderings (MAOs). Henzinger showed for every MAO and every $1 leq k leq (where $ is the minimum degree of the graph) the existence of $k$ internally vertexdisjoint 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 nonconstructive. We present the first algorithm that computes these $k$ internally vertexdisjoint paths in linear time $O(m)$, which improves the previously best time $O(mink,nm)$. 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. 

@inproceedings{Preisser2018, author = {J. E. Prei{\ss}er and J. M. Schmidt}, title = {Computing VertexDisjoint Paths in Large Graphs using {MAO}s}, booktitle = {Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC'18)}, year = {2018}, series_ = {Leibniz International Proceedings in Informatics (LIPIcs)}, volume_ = {123}, pages = {13:113:12}, doi = {http://dx.doi.org/10.4230/LIPIcs.ISAAC.2018.13} }  
A. Schmid and J. M. Schmidt. Computing 2Walks in Polynomial Time. ACM Transactions on Algorithms, 14(2):22.122.18, 2018.  
Abstract: A 2walk 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 3connected planar graph contains a closed 2walk such that all vertices visited twice are contained in 3separators. This seminal result generalizes Tutte's theorem that every 4connected planar graph is Hamiltonian as well as Barnette's theorem that every 3connected planar graph has a spanning tree with maximum degree at most 3. The algorithmic challenge of finding such a closed 2walk 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 edgedisjoint. This implies the first polynomialtime algorithm that computes the closed 2walk mentioned above. Its running time is O(n^3). 

@article{Schmid2018, author = {A. Schmid and J. M. Schmidt}, title = {Computing 2Walks in Polynomial Time}, journal = {ACM Transactions on Algorithms}, year = {2018}, volume = {14}, number = {2}, pages = {22.122.18}, doi = {http://dx.doi.org/10.1145/3183368} }  
A. Schmid and J. M. Schmidt. Computing Tutte Paths. In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP'18), pages 98:198:14, 2018.  
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 nonconstructive, 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 4connected planar graphs, Tutte paths are in fact Hamiltonian paths and Chiba and Nishizeki showed how to compute such paths in linear time. For 3connected 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. However, Tutte paths are defined for general 2connected 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 efficient algorithm that computes a Tutte path (in this unrestricted setting). One of the strongest existence results about such Tutte paths is due to Sanders, 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 efficiently. Our method refines both, the existence results of Thomassen and Sanders, and avoids that the subgraphs arising in the inductive proof intersect in more than one edge by using a novel iterative decomposition along 2separators. Finally, we show that our algorithm runs in time O(n^2). 

@inproceedings{Schmid2018b, author = {A. Schmid and J. M. Schmidt}, title = {Computing {T}utte Paths}, booktitle = {Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP'18)}, year = {2018}, pages = {98:198:14}, doi = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.98} }  
J. M. Schmidt. Tight bounds for the vertices of degree k in minimally kconnected graphs. Journal of Graph Theory, 88(1):146153, 2018.  
Abstract: For minimally kconnected graphs on n vertices, Mader proved a tight lower bound for the number V_k 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 longstanding 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. 

@article{Schmidt2017, author = {J. M. Schmidt}, title = {Tight bounds for the vertices of degree k in minimally kconnected graphs}, journal = {Journal of Graph Theory}, year = {2018}, volume = {88}, number = {1}, pages = {146153}, doi = {http://dx.doi.org/10.1002/jgt.22202} }  
K. Mehlhorn, A. Neumann and J. M. Schmidt. Certifying 3EdgeConnectivity. Algorithmica, 77(2):309335, 2017.  
Abstract: We present a certifying algorithm that tests graphs for 3edgeconnectivity; the algorithm works in linear time. If the input graph is not 3edgeconnected, the algorithm returns a 2edgecut. If it is 3edgeconnected, 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 3edgeconnectivity. Additionally, we show how to compute and certify the 3edgeconnected components and a cactus representation of the 2cuts in linear time. For 3vertexconnectivity, we show how to compute the 3vertexconnected components of a 2connected graph. 

@article{Mehlhorn2017, author = {K. Mehlhorn and A. Neumann and J. M. Schmidt}, title = {Certifying 3EdgeConnectivity}, journal = {Algorithmica}, year = {2017}, volume = {77}, number = {2}, pages = {309335}, doi = {http://dx.doi.org/10.1007/s004530150075x}, issn = {01784617} }  
L. Schlipf and J. M. Schmidt. EdgeOrders. In Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP'17), pages 75:175:14, 2017.  
Abstract: Canonical orderings and their relatives such as stnumberings 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 wellknown graph decompositions into parts that have a prescribed vertexconnectivity. Despite extensive interest in canonical orderings, no analogue of this unifying concept is known for edgeconnectivity. In this paper, we establish such a concept named edgeorders and show how to compute (1,1)edgeorders of 2edgeconnected graphs as well as (2,1)edgeorders of 3edgeconnected graphs in linear time, respectively. While the former can be seen as the edgevariants of stnumberings, the latter are the edgevariants of Mondshein sequences and nonseparating ear decompositions. The methods that we use for obtaining such edgeorders differ considerably in almost all details from the ones used for their vertexcounterparts, as different graphtheoretic constructions are used in the inductive proof and standard reductions from edge to vertexconnectivity are bound to fail. As a first application, we consider the famous EdgeIndependent Spanning Tree Conjecture, which asserts that every $k$edgeconnected graph contains $k$ rooted spanning trees that are pairwise edgeindependent. We illustrate the impact of the above edgeorders by deducing algorithms that construct 2 and 3edge independent spanning trees of 2 and 3edgeconnected graphs, the latter of which improves the best known running time from $O(n^2)$ to linear time. 

@inproceedings{Schlipf2017, author = {L. Schlipf and J. M. Schmidt}, title = {EdgeOrders}, booktitle = {Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP'17)}, year = {2017}, pages = {75:175:14}, doi = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.75} }  
A. Adamaszek, M. Adamaszek, M. Mnich and J. M. Schmidt. Lower bounds for locally highly connected graphs. Graphs and Combinatorics, 32(5):16411650, 2016.  
Abstract: We propose a conjecture regarding the lower bound for the number of edges in locally kconnected graphs and we prove it for k=2. In particular, we show that every connected locally 2connected graph is M_3rigid. For the special case of surface triangulations, this fact was known before using topological methods. We generalize this result to all locally 2connected graphs and give a purely combinatorial proof. Our motivation to study locally kconnected graphs comes from lower bound conjectures for flag triangulations of manifolds, and we discuss some more specific problems in this direction. 

@article{Adamaszek2016, author = {A. Adamaszek and M. Adamaszek and M. Mnich and J. M. Schmidt}, title = {Lower bounds for locally highly connected graphs}, journal = {Graphs and Combinatorics}, year = {2016}, volume = {32}, number = {5}, pages = {16411650}, doi = {http://dx.doi.org/10.1007/s003730161686y} }  
H. Alt, M. S. Payne, J. M. Schmidt and D. R. Wood. Thoughts on Barnette's conjecture. The Australasian Journal of Combinatorics, 64(2):354365, 2016.  
Abstract: We prove a new sufficient condition for a cubic 3connected 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 3connected 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 redgreen 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 selfcontained proofs have not been published. 

@article{Alt2016, author = {H. Alt and M. S. Payne and J. M. Schmidt and D. R. Wood}, title = {Thoughts on {B}arnette's conjecture}, journal = {The Australasian Journal of Combinatorics}, year = {2016}, volume = {64}, number = {2}, pages = {354365}, url = {http://ajc.maths.uq.edu.au/pdf/64/ajc_v64_p354.pdf} }  
M. Mnich, I. Rutter and J. M. Schmidt. LinearTime Recognition of Map Graphs with Outerplanar Witness. In Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'16), pages 5:15:14, 2016.  
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 polynomialtime recognition algorithm for map graphs. However, the run time of this algorithm is estimated to be Omega(n^120) for nvertex 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. 

@inproceedings{Mnich2016, author = {M. Mnich and I. Rutter and J. M. Schmidt}, title = {LinearTime Recognition of Map Graphs with Outerplanar Witness}, booktitle = {Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'16)}, year = {2016}, series_ = {LIPIcs}, pages = {5:15:14}, doi = {http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.5} }  
J. M. Schmidt. Mondshein Sequences (a.k.a. (2,1)Orders). SIAM Journal on Computing, 45(6):19852003, 2016.  
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 farreaching generalization of canonical orderings to nonplanar graphs that was published by Lee Mondshein in a PhDthesis 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 2connected 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 nonseparating ear decomposition. Surprisingly, this fundamental link between canonical orderings and nonseparating ear decomposition has not been established before. 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 followup 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 lineartime algorithms for five other problems, for four out of which the previous best running times have been quadratic. In particular, we show how to  compute three independent spanning trees in a 3connected graph in time O(m), improving a result of Cheriyan and Maheshwari [J. Algorithms 9(4)], 

@article{Schmidt2016, author = {J. M. Schmidt}, title = {{M}ondshein Sequences (a.k.a. (2,1)Orders)}, journal = {SIAM Journal on Computing}, year = {2016}, volume = {45}, number = {6}, pages = {19852003}, doi = {http://dx.doi.org/10.1137/15M1030030} }  
T. Biedl and J. M. Schmidt. SmallArea Orthogonal Drawings of 3Connected Graphs. In Proceedings of the 23rd International Symposium on Graph Drawing (GD'15), pages 153165, 2015.  
Abstract: It is wellknown that every graph with maximum degree 4 has an orthogonal drawing with area at most 4964 n^2+O(n) approx 0.76n^2. In this paper, we show that if the graph is 3connected, then the area can be reduced even further to 916n^2+O(n) approx 0.56n^2. The drawing uses the 3canonical order for (not necessarily planar) 3connected 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.  
@inproceedings{Biedl2015, author = {T. Biedl and J. M. Schmidt}, title = {SmallArea Orthogonal Drawings of 3Connected Graphs}, booktitle = {Proceedings of the 23rd International Symposium on Graph Drawing (GD'15)}, year = {2015}, series_ = {LNCS}, volume_ = {9411}, pages = {153165}, doi = {http://dx.doi.org/10.1007/9783319272610_13} }  
T. Miltzow, J. M. Schmidt and M. Xia. Counting K_4Subdivisions. Discrete Mathematics, 338(12):23872392, 2015.  
Abstract: A fundamental theorem in graph theory states that any 3connected graph contains a subdivision of K_4. As a generalization, we ask for the minimum number of K_4subdivisions that are contained in every 3connected graph on n vertices. We prove that there are Omega(n^3) such K_4subdivisions 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_4subdivisions is Phard.  
@article{Miltzow2015, author = {T. Miltzow and J. M. Schmidt and M. Xia}, title = {Counting {K}$_4$Subdivisions}, journal = {Discrete Mathematics}, year = {2015}, volume = {338}, number = {12}, pages = {23872392}, doi = {http://dx.doi.org/10.1016/j.disc.2015.06.004} }  
A. Schmid and J. M. Schmidt. Computing 2Walks in Polynomial Time. In Proceedings of the 32nd Symposium on Theoretical Aspects of Computer Science (STACS'15), pages 676688, 2015.  
Abstract: A 2walk 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 3connected planar graph contains a closed 2walk such that all vertices visited twice are contained in 3separators. This seminal result generalizes Tutte's theorem that every 4connected planar graph is Hamiltonian as well as Barnette's theorem that every 3connected planar graph has a spanning tree with maximum degree at most 3. The algorithmic challenge of finding such a closed 2walk 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 edgedisjoint. This implies the first polynomialtime algorithm that computes the closed 2walk mentioned above. 

@inproceedings{Schmid2015, author = {A. Schmid and J. M. Schmidt}, title = {Computing 2Walks in Polynomial Time}, booktitle = {Proceedings of the 32nd Symposium on Theoretical Aspects of Computer Science (STACS'15)}, year = {2015}, series_ = {LIPIcs}, volume_ = {30}, pages = {676688}, doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2015.676} }  
J. M. Schmidt and P. Valtr. Cubic Plane Graphs on a Given Point Set. Computational Geometry, 48:113, 2015.  
Abstract: Let P be a set of n > 3 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 2connected) cubic plane straightline graph on P. No polynomialtime 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 polynomialtime algorithm that checks for 2connected cubic plane graphs; 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., a cubic plane graph on P implies a connected cubic plane graph on P, and a 2connected cubic plane graph on P implies a 2connected 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(n^3).  
@article{Schmidt2015, author = {J. M. Schmidt and P. Valtr}, title = {Cubic Plane Graphs on a Given Point Set}, journal = {Computational Geometry}, year = {2015}, volume = {48}, pages = {113}, doi = {http://dx.doi.org/10.1016/j.comgeo.2014.06.001} }  
C. Doerr, G. Ramakrishna and J. M. Schmidt. Computing Minimum Cycle Bases in Weighted Partial 2Trees in Linear Time. Journal of Graph Algorithms and Applications, 18(3):325346, 2014.  
Abstract: We present a linear time algorithm for computing an implicit linear space representation of a minimum cycle basis in weighted partial 2trees (i.e., graphs of treewidth at most two) with nonnegative edgeweights. 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 WulffNilsen [Min stcut Oracle for Planar Graphs with NearLinear Preprocessing Time, FOCS 2010] showed how to compute an implicit O(n log n) space representation of an minimum cycle basis in O(n log^5 n) time. For the special case of partial 2trees, 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:970974, 2010]. 

@article{Doerr2014, author = {C. Doerr and G. Ramakrishna and J. M. Schmidt}, title = {Computing Minimum Cycle Bases in Weighted Partial 2Trees in Linear Time}, journal = {Journal of Graph Algorithms and Applications}, year = {2014}, volume = {18}, number = {3}, pages = {325346}, doi = {http://dx.doi.org/10.7155/jgaa.00325} }  
M. S. Payne, J. M. Schmidt and D. R. Wood. Which point sets admit a kangulation?. Journal of Computational Geometry, 5(1):4155, 2014.  
Abstract: For k >= 3, a kangulation is a 2connected plane graph in which every internal face is a kgon. We say that a point set P admits a plane graph G if there is a straightline 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 kangulation and find that, for sets containing at least 2k^2 points, the only obstructions are those that follow from Euler's formula.  
@article{Payne2014, author = {M. S. Payne and J. M. Schmidt and D. R. Wood}, title = {Which point sets admit a kangulation?}, journal = {Journal of Computational Geometry}, year = {2014}, volume = {5}, number = {1}, pages = {4155}, url = {http://jocg.org/index.php/jocg/article/view/92} }  
J. M. Schmidt. The Mondshein Sequence. In Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14), pages 967978, 2014.  
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 farreaching generalization of canonical orderings to nonplanar graphs that was published by Lee Mondshein in a PhDthesis 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 2connected 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 nonseparating 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 followup 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 lineartime 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 3connected graph in linear time, improving a result of Cheriyan and Maheshwari [J. Algorithms 9(4)]. Secondly, we improve the preprocessing time for the outputsensitive data structure by Di Battista, Tamassia and Vismara [Algorithmica 23(4)] that reports three internally disjoint paths between any given vertex pair from O(n^2) to O(m). Finally, we show how a very simple lineartime planarity test can be derived once a Mondshein sequence is computed. 

@inproceedings{Schmidt2014, author = {J. M. Schmidt}, title = {The {M}ondshein Sequence}, booktitle = {Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14)}, year = {2014}, series_ = {LNCS}, volume_ = {8572}, pages = {967978}, doi = {http://dx.doi.org/10.1007/9783662439487_80} }  
C. Doerr, G. Ramakrishna and J. M. Schmidt. Computing Minimum Cycle Bases in Weighted Partial 2Trees in Linear Time. In 39th International Workshop on GraphTheoretic Concepts in Computer Science (WG'13), pages 225236, 2013.  
Abstract: We present a linear time algorithm for computing an implicit linear space representation of a minimum cycle basis (MCB) in weighted partial 2trees, 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 WulffNilsen [Min $st$cut Oracle for Planar Graphs with NearLinear Preprocessing Time, FOCS 2010] showed how to compute an implicit O(n log n) space representation of an MCB in O(n log^5 n) time. For the special case of partial 2trees, 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:970974, 2010]. 

@inproceedings{Doerr2013, author = {C. Doerr and G. Ramakrishna and J. M. Schmidt}, title = {Computing Minimum Cycle Bases in Weighted Partial 2Trees in Linear Time}, booktitle = {39th International Workshop on GraphTheoretic Concepts in Computer Science (WG'13)}, year = {2013}, series_ = {LNCS}, volume_ = {8165}, pages = {225236}, doi = {http://dx.doi.org/10.1007/9783642450433_20} }  
A. Elmasry, K. Mehlhorn and J. M. Schmidt. Every DFS tree of a 3connected graph contains a contractible edge. Journal of Graph Theory, 72(1):112121, 2013.  
Abstract: Tutte proved that every 3connected graph G on more than 4 vertices contains a contractible edge. We strengthen this result by showing that every depthfirstsearch tree of G contains a contractible edge. Moreover, we show that every spanning tree of G contains a contractible edge if G is 3regular or if G does not contain two disjoint pairs of adjacent degree3 vertices.  
@article{Elmasry2013, author = {A. Elmasry and K. Mehlhorn and J. M. Schmidt}, title = {Every {DFS} tree of a 3connected graph contains a contractible edge}, journal = {Journal of Graph Theory}, year = {2013}, volume = {72}, number = {1}, pages = {112121}, doi = {http://dx.doi.org/10.1002/jgt.21635} }  
K. Mehlhorn, A. Neumann and J. M. Schmidt. Certifying 3EdgeConnectivity. In 39th International Workshop on GraphTheoretic Concepts in Computer Science (WG'13), pages 358369, 2013.  
Abstract: We present a linear time certifying algorithm that tests graphs for 3edgeconnectivity. If the input graph G is not 3edgeconnected, the algorithm returns a 2edgecut. If G is 3edgeconnected, the algorithm returns a construction sequence that constructs G from the graph with two nodes and three parallel edges using only operations that preserve 3edgeconnectivity. No previous algorithm returned a certificate in the case of a 3edgeconnected input graph.  
@inproceedings{Mehlhorn2013, author = {K. Mehlhorn and A. Neumann and J. M. Schmidt}, title = {Certifying 3EdgeConnectivity}, booktitle = {39th International Workshop on GraphTheoretic Concepts in Computer Science (WG'13)}, year = {2013}, series_ = {LNCS}, volume_ = {8165}, pages = {358369}, doi = {http://dx.doi.org/10.1007/9783642450433_31} }  
J. M. Schmidt. Contractions, Removals and Certifying 3Connectivity in Linear Time. SIAM Journal on Computing, 42(2):494535, 2013.  
Abstract: One of the most noted construction methods of 3vertexconnected graphs is due to Tutte and based on the following fact: Any 3vertexconnected graph G=(V,E) on more than 4 vertices contains a contractible edge, i.e., an edge whose contraction generates a 3connected graph. This implies the existence of a sequence of edge contractions from G to the complete graph K_4, such that every intermediate graph is 3vertexconnected. 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 lineartime test of 3connectivity that is certifying; finding such an algorithm has been a major open problem in the design of certifying algorithms in the last years. The test is conceptually different from wellknown lineartime 3connectivity 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 3edgeconnectivity. 

@article{Schmidt2013, author = {J. M. Schmidt}, title = {Contractions, Removals and Certifying 3Connectivity in Linear Time}, journal = {SIAM Journal on Computing}, year = {2013}, volume = {42(2)}, pages = {494535}, doi = {http://dx.doi.org/10.1137/110848311} }  
J. M. Schmidt. A Simple Test on 2Vertex and 2EdgeConnectivity. Information Processing Letters, 113(7):241244, 2013.  
Abstract: Testing a graph on 2vertex and 2edgeconnectivity are two fundamental algorithmic graph problems. For both problems, different lineartime algorithms with simple implementations are known. Here, an even simpler lineartime algorithm is presented that computes a structure from which both the 2vertex and 2edgeconnectivity of a graph can be easily ``read off''. The algorithm computes all bridges and cut vertices of the input graph in the same time.  
@article{Schmidt2013a, author = {J. M. Schmidt}, title = {A Simple Test on 2Vertex and 2EdgeConnectivity}, journal = {Information Processing Letters}, year = {2013}, volume = {113}, number = {7}, pages = {241244}, doi = {http://dx.doi.org/10.1016/j.ipl.2013.01.016} }  
J. M. Schmidt. A Planarity Test via Construction Sequences. In 38th International Symposium on Mathematical Foundations of Computer Science (MFCS'13), pages 765776, 2013.  
Abstract: Lineartime 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 lineartime tests. We give a conceptually simple reduction from planarity testing to the problem of computing a certain construction of a 3connected graph. This implies a lineartime planarity test. Our approach is radically different from all previous lineartime planarity tests; as key concept, we maintain a planar embedding that is 3connected at each point in time. The algorithm computes a planar embedding if the input graph is planar and a Kuratowskisubdivision otherwise.  
@inproceedings{Schmidt2013b, author = {J. M. Schmidt}, title = {A Planarity Test via Construction Sequences}, booktitle = {38th International Symposium on Mathematical Foundations of Computer Science (MFCS'13)}, year = {2013}, series_ = {LNCS}, volume_ = {8087}, pages = {765776}, doi = {http://dx.doi.org/10.1007/9783642403132_67} }  
A. Elmasry, K. Mehlhorn and J. M. Schmidt. An O(n+m) Certifying Triconnnectivity Algorithm for Hamiltonian Graphs. Algorithmica, 62(3):754766, 2012.  
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. 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.  
@article{Elmasry2012, author = {A. Elmasry and K. Mehlhorn and J. M. Schmidt}, title = {An {O(n+m)} Certifying Triconnnectivity Algorithm for {H}amiltonian Graphs}, journal = {Algorithmica}, year = {2012}, volume = {62}, number = {3}, pages = {754766}, doi = {http://dx.doi.org/10.1007/s0045301094812} }  
C. Knauer, L. Schlipf, J. M. Schmidt and H. R. Tiwary. Largest Inscribed Rectangles in Convex Polygons. Journal of Discrete Algorithms, 13:7885, 2012.  
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 (1epsilon) times the optimum with probability t in time O(log n / epsilon) for any constant t < 1. We further give a deterministic approximation algorithm that computes an inscribed rectangle of area at least (1epsilon) times the optimum in running time O(log n / epsilon^2) and show how this running time can be slightly improved.  
@article{Knauer2012, author = {C. Knauer and L. Schlipf and J. M. Schmidt and H. R. Tiwary}, title = {Largest Inscribed Rectangles in Convex Polygons}, journal = {Journal of Discrete Algorithms}, year = {2012}, volume = {13}, pages = {7885}, doi = {http://dx.doi.org/10.1016/j.jda.2012.01.002} }  
J. M. Schmidt. Construction Sequences and Certifying 3Connectivity. Algorithmica, 62:192208, 2012.  
Abstract: Tutte proved that every 3vertexconnected 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_4 can be computed in O(V^2) time by extending Barnette's and Grünbaum's theorem. As an application, we derive a certificate for the 3vertexconnectivity of graphs that can be easily computed and verified.  
@article{Schmidt2012, author = {J. M. Schmidt}, title = {Construction Sequences and Certifying 3Connectivity}, journal = {Algorithmica}, year = {2012}, volume = {62}, pages = {192208}, doi = {http://dx.doi.org/10.1007/s0045301094509} }  
J. M. Schmidt and P. Valtr. Cubic Plane Graphs on a Given Point Set. In Proceedings of the 28th Annual Symposium on Computational Geometry (SoCG'12), pages 201208, 2012.  
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 straightline graph on P. No polynomialtime 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 polynomialtime 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 2connected cubic plane graph, we show that P admits also a 2connected cubic plane graph that contains the boundary cycle of P. The algorithm extends to checking P on admitting a 2connected cubic plane graph.  
@inproceedings{Schmidt2012a, author = {J. M. Schmidt and P. Valtr}, title = {Cubic Plane Graphs on a Given Point Set}, booktitle = {Proceedings of the 28th Annual Symposium on Computational Geometry (SoCG'12)}, year = {2012}, pages = {201208}, doi = {http://dx.doi.org/10.1145/2261250.2261281}, isbn = {9781450312998} }  
J. M. Schmidt. Certifying 3Connectivity in Linear Time. In Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP'12), pages 786797, 2012.  
Abstract: One of the most noted construction methods of 3vertexconnected graphs is due to Tutte and based on the following fact: Every 3vertexconnected graph G on more than 4 vertices contains a contractible edge, i.e., an edge whose contraction generates a 3connected graph. This implies the existence of a sequence of edge contractions from G to K_4 such that every intermediate graph is 3vertexconnected. A theorem of Barnette and Grünbaum yields 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). Based on this result, we give a lineartime test of 3connectivity that is certifying; finding such an algorithm has been a major open problem in the design of certifying algorithms in the last years. The 3connectivity test is conceptually different from wellknown lineartime tests on 3connectivity; it 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 3edgeconnectivity. 

@inproceedings{Schmidt2012b, author = {J. M. Schmidt}, title = {Certifying 3Connectivity in Linear Time}, booktitle = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP'12)}, year = {2012}, series_ = {LNCS}, volume_ = {7391}, pages = {786797}, doi = {http://dx.doi.org/10.1007/9783642315947_66} }  
J. M. Schmidt.
Structure and Constructions of 3Connected Graphs. Ph.D. Thesis.
Freie Universität Berlin, Germany,
2011.
[Abstract] [BibTeX] [URL] [PDF] (Ph.D. Thesis) 

Abstract: The class of 3connected (i.e. 3vertexconnected) 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 3connected 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 3connected in linear time. However, the lineartime 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 easytoverify certificate of correctness for that output. However, surprisingly few work has been devoted to find certifying algorithms that test 3connectivity; in fact, the currently fastest algorithms need quadratic time. Two classic results in graph theory due to Barnette, Grünbaum and Tutte show that 3connected 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 lineartime certifying algorithm for testing 3connectivity, which is based on these constructions. This yields also simple certifying algorithms in linear time for 2connectivity, 2edgeconnectivity and 3edgeconnectivity. We conclude this thesis by a structural result that shows that one of the constructions is preserved when being applied to depthfirst trees of the graph only. 

@phdthesis{Schmidt2011, author = {J. M. Schmidt}, title = {Structure and Constructions of 3Connected Graphs}, school = {Freie Universit\"at Berlin, Germany}, year = {2011}, url = {http://www.diss.fuberlin.de/diss/receive/FUDISS_thesis_000000022941} }  
J. M. Schmidt. Construction Sequences and Certifying 3Connectedness. In Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science (STACS'10), pages 633644, 2010.  
Abstract: Tutte proved that every 3connected graph on more than 4 nodes has a contractible edge. Barnette and Gruenbaum 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 K_4 can be computed in O(V^2) time by extending Barnette and Gruenbaum's theorem. As an application, we derive a certificate for the 3connectedness of graphs that can be easily computed and verified.  
@inproceedings{Schmidt2010, author = {J. M. Schmidt}, title = {Construction Sequences and Certifying 3Connectedness}, booktitle = {Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science (STACS'10)}, year = {2010}, series_ = {Leibniz International Proceedings in Informatics (LIPIcs)}, volume_ = {5}, pages = {633644}, doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2491}, issn = {18688969}, isbn = {9783939897163} }  
J. M. Schmidt. Interval Stabbing Problems in Small Integer Ranges. In Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC'09), pages 163172, 2009.  
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).  
@inproceedings{Schmidt2009a, author = {J. M. Schmidt}, title = {Interval Stabbing Problems in Small Integer Ranges}, booktitle = {Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC'09)}, year = {2009}, series_ = {LNCS}, volume_ = {5878}, pages = {163172}, doi = {http://dx.doi.org/10.1007/9783642106316_18}, isbn = {9783642106309} }  
M. Chimani, P. Mutzel and J. M. Schmidt. Efficient Extraction of Multiple Kuratowski Subdivisions. In Proceedings of the 15th International Symposium on Graph Drawing (GD'07), pages 159170, 2007.  
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 nonplanarity. 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., BranchandCut 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.  
@inproceedings{Chimani2007, author = {M. Chimani and P. Mutzel and J. M. Schmidt}, title = {Efficient Extraction of Multiple {K}uratowski {S}ubdivisions}, booktitle = {Proceedings of the 15th International Symposium on Graph Drawing (GD'07)}, year = {2007}, series_ = {LNCS}, volume_ = {4875}, pages = {159170}, doi = {http://dx.doi.org/10.1007/9783540775379_17}, issn = {03029743 (Print) 16113349 (Online)}, isbn = {9783540775362} }  
J. M. Schmidt.
Effiziente Extraktion von KuratowskiTeilgraphen.
Diploma Thesis.
Technische Universität Dortmund, Germany,
2007.
[Abstract] [BibTeX] [Talk] [PDF] (Diploma Thesis) 

Abstract: Ein Graph ist nach dem Satz von Kuratowski genau dann planar, wenn er keine KuratowskiSubdivisions enthält. Eine einzelne davon kann von modernen Planaritätstests bei nicht planaren Eingabegraphen in Linearzeit extrahiert werden. Allerdings existieren Anwendungen, die nicht nur eine, sondern möglichst viele dieser KuratowskiSubdivisions benötigen. Dazu gehören BranchandCutAlgorithmen für einige NPschwere Probleme, wie beispielsweise die Kreuzungsminimierung oder auch verschiedene Varianten des Maximum Planar Subgraph Problems. Die KuratowskiSubdivisions ermöglichen dort die Berechnung von zusätzlichen Nebenbedingungen einer LPRelaxierung. Dabei ist es wünschenswert, dass die KuratowskiSubdivisions paarweise entweder möglichst viele Kanten gemeinsam haben oder weitgehend kantendisjunkt sind. In dieser Diplomarbeit wird ein Algorithmus entworfen und analysiert, der mehrere KuratowskiSubdivisions in linearer Zeit O(n + m + Sum_(K in S) E(K)) extrahieren kann, wobei S die Menge der gefundenen KuratowskiSubdivisions ist. Dieser Algorithmus stellt eine Erweiterung des aktuellen Planaritätstests von Boyer und Myrvold dar und kann zusätzlich so modifiziert werden, dass entweder möglichst ähnliche oder möglichst verschiedene KuratowskiSubdivisions ausgegeben werden. Die Laufzeit des Algorithmus ist dabei asymptotisch optimal. Aus diesem Algorithmus wird ein zweiter Ansatz entwickelt, der in der Praxis mehr KuratowskiSubdivisions extrahieren kann, dafür aber zu einer superlinearen Laufzeit führt. Beide Verfahren werden implementiert und deren Praxistauglichkeit verglichen. 

@mastersthesis{Schmidt2007, author = {J. M. Schmidt}, title = {Effiziente {E}xtraktion von {K}uratowski{T}eilgraphen}, type = {Diploma Thesis}, school = {Technische Universit\"at Dortmund, Germany}, year = {2007}, issn = {18644503} }  
B. Baranski, T. BartzBeielstein, R. Ehlers, T. Kajendran, B. Kosslers, J. Mehnen, T. Polazek, R. Reimholz, J. M. Schmidt, K. Schmitt, D. Seis, R. Slodzinski, S. Steeg, N. Wiemann and M. Zimmermann. Highorder punishment and the evolution of cooperation. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'06), pages 379380, 2006.  
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 highorder punishment opportunities can maintain a higher cooperation level in an agent based simulation of the evolution of cooperation.  
@inproceedings{Baranski2006, author = {B. Baranski and T. BartzBeielstein and R. Ehlers and T. Kajendran and B. Kosslers and J. Mehnen and T. Polazek and R. Reimholz and J. M. Schmidt and K. Schmitt and D. Seis and R. Slodzinski and S. Steeg and N. Wiemann and M. Zimmermann}, title = {Highorder punishment and the evolution of cooperation}, booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'06)}, year = {2006}, pages = {379380}, doi = {http://dx.doi.org/10.1145/1143997.1144065}, isbn = {1595931864} }  
B. Baranski, T. BartzBeielstein, R. Ehlers, T. Kajendran, B. Kosslers, J. Mehnen, T. Polazek, R. Reimholz, J. M. Schmidt, K. Schmitt, D. Seis, R. Slodzinski, S. Steeg, N. Wiemann and M. Zimmermann. The impact of group reputation in multiagent environments. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC'06), pages 12241231, 2006.  
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 viceversa. 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 ingroup and increases cooperation with the outgroup.  
@inproceedings{Baranski2006a, author = {B. Baranski and T. BartzBeielstein and R. Ehlers and T. Kajendran and B. Kosslers and J. Mehnen and T. Polazek and R. Reimholz and J. M. Schmidt and K. Schmitt and D. Seis and R. Slodzinski and S. Steeg and N. Wiemann and M. Zimmermann}, title = {The impact of group reputation in multiagent environments}, booktitle = {Proceedings of the IEEE Congress on Evolutionary Computation (CEC'06)}, year = {2006}, pages = {12241231}, doi = {http://dx.doi.org/10.1109/CEC.2006.1688449} } 
Created on 20200324