M. Mnich, I. Rutter and J. M. Schmidt. LinearTime Recognition of Map Graphs with Outerplanar Witness. Discrete Optimization, to appear.  
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{Mnich2017, author = {M. Mnich and I. Rutter and J. M. Schmidt}, title = {LinearTime Recognition of Map Graphs with Outerplanar Witness}, journal = {Discrete Optimization}, year = {to appear} }  
J. M. Schmidt. Tight bounds for the vertices of degree k in minimally kconnected graphs. Journal of Graph Theory, to appear.  
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 = {to appear}, 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] [Talk] [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} }  
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_ = {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 20171205