Publications by Jens M. Schmidt (only peer-refereed)

QuickSearch:   Number of matching entries: 0.

Search Settings

M. Mnich, I. Rutter and J. M. Schmidt. Linear-Time 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 polynomial-time recognition algorithm for map graphs. However, the run time of this algorithm is estimated to be n^120) for n-vertex graphs, and a full description of its details remains unpublished.

We give a new and purely combinatorial algorithm that decides whether a graph G is a map graph having an outerplanar witness W. This is a step towards a first combinatorial recognition algorithm for general map graphs. The algorithm runs in time and space O(n+m). In contrast to Thorup's approach, it computes the witness graph W in the affirmative case.

@article{Mnich2017,
  author = {M. Mnich and I. Rutter and J. M. Schmidt},
  title = {Linear-Time 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 k-connected graphs. Journal of Graph Theory, to appear.
Abstract: For minimally k-connected 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 long-standing one only for small values of m. We prove that this new bound is best possible. The bound contains Mader's bound as special case.

@article{Schmidt2017,
  author = {J. M. Schmidt},
  title = {Tight bounds for the vertices of degree k in minimally k-connected 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 3-Edge-Connectivity. Algorithmica, 77(2):309-335, 2017.
Abstract: We present a certifying algorithm that tests graphs for 3-edge-connectivity; the algorithm works in linear time. If the input graph is not 3-edge-connected, the algorithm returns a 2-edge-cut. If it is 3-edge-connected, it returns a construction sequence that constructs the input graph from the graph with two vertices and three parallel edges using only operations that (obviously) preserve 3-edge-connectivity.

Additionally, we show how to compute and certify the 3-edge-connected components and a cactus representation of the 2-cuts in linear time. For 3-vertex-connectivity, we show how to compute the 3-vertex-connected components of a 2-connected graph.

@article{Mehlhorn2017,
  author = {K. Mehlhorn and A. Neumann and J. M. Schmidt},
  title = {Certifying 3-Edge-Connectivity},
  journal = {Algorithmica},
  year = {2017},
  volume = {77},
  number = {2},
  pages = {309-335},
  doi = {http://dx.doi.org/10.1007/s00453-015-0075-x},
  issn = {0178-4617}
}
L. Schlipf and J. M. Schmidt. Edge-Orders. In Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP'17), pages 75:1-75:14, 2017.
Abstract: Canonical orderings and their relatives such as st-numberings have been used as a key tool in algorithmic graph theory for the last decades. Recently, a unifying link behind all these orders has been shown that links them to well-known graph decompositions into parts that have a prescribed vertex-connectivity.

Despite extensive interest in canonical orderings, no analogue of this unifying concept is known for edge-connectivity. In this paper, we establish such a concept named edge-orders and show how to compute (1,1)-edge-orders of 2-edge-connected graphs as well as (2,1)-edge-orders of 3-edge-connected graphs in linear time, respectively. While the former can be seen as the edge-variants of st-numberings, the latter are the edge-variants of Mondshein sequences and non-separating ear decompositions. The methods that we use for obtaining such edge-orders differ considerably in almost all details from the ones used for their vertex-counterparts, as different graph-theoretic constructions are used in the inductive proof and standard reductions from edge- to vertex-connectivity are bound to fail.

As a first application, we consider the famous Edge-Independent Spanning Tree Conjecture, which asserts that every $k$-edge-connected graph contains $k$ rooted spanning trees that are pairwise edge-independent. We illustrate the impact of the above edge-orders by deducing algorithms that construct 2- and 3-edge independent spanning trees of 2- and 3-edge-connected graphs, the latter of which improves the best known running time from $O(n^2)$ to linear time.

@inproceedings{Schlipf2017,
  author = {L. Schlipf and J. M. Schmidt},
  title = {Edge-Orders},
  booktitle = {Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP'17)},
  year = {2017},
  pages = {75:1--75: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):1641-1650, 2016.
Abstract: We propose a conjecture regarding the lower bound for the number of edges in locally k-connected graphs and we prove it for k=2. In particular, we show that every connected locally 2-connected graph is M_3-rigid. For the special case of surface triangulations, this fact was known before using topological methods. We generalize this result to all locally 2-connected graphs and give a purely combinatorial proof.

Our motivation to study locally k-connected graphs comes from lower bound conjectures for flag triangulations of manifolds, and we discuss some more specific problems in this direction.

@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 = {1641-1650},
  doi = {http://dx.doi.org/10.1007/s00373-016-1686-y}
}
H. Alt, M. S. Payne, J. M. Schmidt and D. R. Wood. Thoughts on Barnette's conjecture. The Australasian Journal of Combinatorics, 64(2):354-365, 2016.
Abstract: We prove a new sufficient condition for a cubic 3-connected planar graph to be Hamiltonian. This condition is most easily described as a property of the dual graph. Let G be a planar triangulation. Then the dual G* is a cubic 3-connected planar graph, and G* is bipartite if and only if G is Eulerian. We prove that if the vertices of G are (improperly) coloured blue and red, such that the blue vertices cover the faces of G, there is no blue cycle, and every red cycle contains a vertex of degree at most 4, then G* is Hamiltonian.

This result implies the following special case of Barnette's Conjecture: if G is an Eulerian planar triangulation, whose vertices are properly coloured blue, red and green, such that every red-green cycle contains a vertex of degree 4, then G* is Hamiltonian. Our final result highlights the limitations of using a proper colouring of G as a starting point for proving Barnette's Conjecture. We also explain related results on Barnette's Conjecture that were obtained by Kelmans and for which detailed self-contained proofs have not been published.

@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 = {354-365},
  url = {http://ajc.maths.uq.edu.au/pdf/64/ajc_v64_p354.pdf}
}
M. Mnich, I. Rutter and J. M. Schmidt. Linear-Time Recognition of Map Graphs with Outerplanar Witness. In Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'16), pages 5:1-5: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 polynomial-time recognition algorithm for map graphs. However, the run time of this algorithm is estimated to be Omega(n^120) for n-vertex graphs, and a full description of its details remains unpublished.

We give a new and purely combinatorial algorithm that decides whether a graph G is a map graph having an outerplanar witness W. This is a step towards a first combinatorial recognition algorithm for general map graphs. The algorithm runs in time and space O(n+m). In contrast to Thorup's approach, it computes the witness graph W in the affirmative case.

@inproceedings{Mnich2016,
  author = {M. Mnich and I. Rutter and J. M. Schmidt},
  title = {Linear-Time 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:1--5: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):1985-2003, 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 far-reaching generalization of canonical orderings to non-planar graphs that was published by Lee Mondshein in a PhD-thesis at M.I.T. as early as 1971.

Mondshein proposed to order the vertices of a graph in a sequence such that, for any i, the vertices from 1 to i induce essentially a 2-connected graph while the remaining vertices from i+1 to n induce a connected graph. Mondshein's sequence generalizes canonical orderings and became later and independently known under the name non-separating ear decomposition. Surprisingly, this fundamental link between canonical orderings and non-separating 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 follow-up work is to improve this running time to subquadratic time.

After putting Mondshein's work into context, we present an algorithm that computes a Mondshein sequence in optimal time and space O(m). This improves the previous best running time by a factor of n. We illustrate the impact of this result by deducing linear-time algorithms for five other problems, 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 3-connected graph in time O(m), improving a result of Cheriyan and Maheshwari [J. Algorithms 9(4)],
- improve the preprocessing time from O(n^2) to O(m) for the output-sensitive data structure by Di Battista, Tamassia and Vismara [Algorithmica 23(4)] that reports three internally disjoint paths between any given vertex pair,
- derive a very simple O(n)-time planarity test once a Mondshein sequence has been computed,
- compute a nested family of contractible subgraphs of 3-connected graphs in time O(m),
- compute a 3-partition in time O(m), while the previous best running time is O(n^2) due to Suzuki et al. [IPSJ 31(5)].

@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 = {1985-2003},
  doi = {http://dx.doi.org/10.1137/15M1030030}
}
T. Biedl and J. M. Schmidt. Small-Area Orthogonal Drawings of 3-Connected Graphs. In Proceedings of the 23rd International Symposium on Graph Drawing (GD'15), pages 153-165, 2015.
Abstract: It is well-known 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 3-connected, then the area can be reduced even further to 916n^2+O(n) approx 0.56n^2. The drawing uses the 3-canonical order for (not necessarily planar) 3-connected graphs, which is a special Mondshein sequence and can hence be computed in linear time. To our knowledge, this is the first application of a Mondshein sequence in graph drawing.
@inproceedings{Biedl2015,
  author = {T. Biedl and J. M. Schmidt},
  title = {Small-Area Orthogonal Drawings of 3-Connected Graphs},
  booktitle = {Proceedings of the 23rd International Symposium on Graph Drawing (GD'15)},
  year = {2015},
  series_ = {LNCS},
  volume_ = {9411},
  pages = {153-165},
  doi = {http://dx.doi.org/10.1007/978-3-319-27261-0_13}
}
T. Miltzow, J. M. Schmidt and M. Xia. Counting K_4-Subdivisions. Discrete Mathematics, 338(12):2387-2392, 2015.
Abstract: A fundamental theorem in graph theory states that any 3-connected graph contains a subdivision of K_4. As a generalization, we ask for the minimum number of K_4-subdivisions that are contained in every 3-connected graph on n vertices. We prove that there are Omega(n^3) such K_4-subdivisions and show that the order of this bound is tight for infinitely many graphs. We further investigate a better bound in dependence on m and prove that the computational complexity of the problem of counting the exact number of K_4-subdivisions is P-hard.
@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 = {2387-2392},
  doi = {http://dx.doi.org/10.1016/j.disc.2015.06.004}
}
A. Schmid and J. M. Schmidt. Computing 2-Walks in Polynomial Time. In Proceedings of the 32nd Symposium on Theoretical Aspects of Computer Science (STACS'15), pages 676-688, 2015.
Abstract: A 2-walk of a graph is a walk visiting every vertex at least once and at most twice. By generalizing decompositions of Tutte and Thomassen, Gao, Richter and Yu proved that every 3-connected planar graph contains a closed 2-walk such that all vertices visited twice are contained in 3-separators. This seminal result generalizes Tutte's theorem that every 4-connected planar graph is Hamiltonian as well as Barnette's theorem that every 3-connected planar graph has a spanning tree with maximum degree at most 3. The algorithmic challenge of finding such a closed 2-walk is to overcome big overlapping subgraphs in the decomposition, which are also inherent in Tutte's and Thomassen's decompositions.

We solve this problem by extending the decomposition of Gao, Richter and Yu in such a way that all pieces, in which the graph is decomposed into, are edge-disjoint. This implies the first polynomial-time algorithm that computes the closed 2-walk mentioned above.

@inproceedings{Schmid2015,
  author = {A. Schmid and J. M. Schmidt},
  title = {Computing 2-Walks in Polynomial Time},
  booktitle = {Proceedings of the 32nd Symposium on Theoretical Aspects of Computer Science (STACS'15)},
  year = {2015},
  series_ = {LIPIcs},
  volume_ = {30},
  pages = {676-688},
  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:1-13, 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 2-connected) cubic plane straight-line graph on P. No polynomial-time algorithm is known for this problem. Based on a reduction to the existence of certain diagonals of the boundary cycle of the convex hull of P, we give the first polynomial-time algorithm that checks for 2-connected cubic plane graphs; the algorithm is constructive and runs in time O(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 2-connected cubic plane graph on P implies a 2-connected cubic plane graph on P that contains the boundary cycle of P. We extend the above algorithm to check for arbitrary cubic plane graphs in time O(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 = {1-13},
  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 2-Trees in Linear Time. Journal of Graph Algorithms and Applications, 18(3):325-346, 2014.
Abstract: We present a linear time algorithm for computing an implicit linear space representation of a minimum cycle basis in weighted partial 2-trees (i.e., graphs of treewidth at most two) with non-negative edge-weights. The implicit representation can be made explicit in a running time that is proportional to the size of the minimum cycle basis.

For planar graphs, Borradaile, Sankowski, and Wulff-Nilsen [Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time, FOCS 2010] showed how to compute an implicit O(n log n) space representation of an minimum cycle basis in O(n log^5 n) time. For the special case of partial 2-trees, our algorithm improves this result to linear time and space. Such an improvement was achieved previously only for outerplanar graphs [Liu and Lu: Minimum Cycle Bases of Weighted Outerplanar Graphs, IPL 110:970--974, 2010].

@article{Doerr2014,
  author = {C. Doerr and G. Ramakrishna and J. M. Schmidt},
  title = {Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time},
  journal = {Journal of Graph Algorithms and Applications},
  year = {2014},
  volume = {18},
  number = {3},
  pages = {325-346},
  doi = {http://dx.doi.org/10.7155/jgaa.00325}
}
M. S. Payne, J. M. Schmidt and D. R. Wood. Which point sets admit a k-angulation?. Journal of Computational Geometry, 5(1):41-55, 2014.
Abstract: For k >= 3, a k-angulation is a 2-connected plane graph in which every internal face is a k-gon. We say that a point set P admits a plane graph G if there is a straight-line drawing of G that maps V(G) onto P and has the same facial cycles and outer face as G. We investigate the conditions under which a point set P admits a k-angulation and find that, for sets containing at least 2k^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 k-angulation?},
  journal = {Journal of Computational Geometry},
  year = {2014},
  volume = {5},
  number = {1},
  pages = {41-55},
  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 967-978, 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 far-reaching generalization of canonical orderings to non-planar graphs that was published by Lee Mondshein in a PhD-thesis at M.I.T. as early as 1971.

Mondshein proposed to order the vertices of a graph in a sequence such that, for any i, the vertices from 1 to i induce essentially a 2-connected graph while the remaining vertices from i+1 to n induce a connected graph. Mondshein's sequence generalizes canonical orderings and became later and independently known under the name non-separating ear decomposition. Currently, the best known algorithm for computing this sequence achieves a running time of O(nm); the main open problem in Mondshein's and follow-up work is to improve this running time to a subquadratic time.

In this paper, we present the first algorithm that computes a Mondshein sequence in time and space O(m), improving the previous best running time by a factor of n. In addition, we illustrate the impact of this result by deducing linear-time algorithms for several other problems, for which the previous best running times have been quadratic.

In particular, we show how to compute three independent spanning trees in a 3-connected graph in linear time, improving a result of Cheriyan and Maheshwari [J. Algorithms 9(4)]. Secondly, we improve the preprocessing time for the output-sensitive data structure by Di Battista, Tamassia and Vismara [Algorithmica 23(4)] that reports three internally disjoint paths between any given vertex pair from O(n^2) to O(m). Finally, we show how a very simple linear-time 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 = {967-978},
  doi = {http://dx.doi.org/10.1007/978-3-662-43948-7_80}
}
C. Doerr, G. Ramakrishna and J. M. Schmidt. Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time. In 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'13), pages 225-236, 2013.
Abstract: We present a linear time algorithm for computing an implicit linear space representation of a minimum cycle basis (MCB) in weighted partial 2-trees, i.e., graphs of treewidth two. The implicit representation can be made explicit in a running time that is proportional to the size of the MCB.

For planar graphs, Borradaile, Sankowski, and Wulff-Nilsen [Min $st$-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time, FOCS 2010] showed how to compute an implicit O(n log n) space representation of an MCB in O(n log^5 n) time. For the special case of partial 2-trees, our algorithm improves this result to linear time and space. Such an improvement was achieved previously only for outerplanar graphs [Liu and Lu: Minimum Cycle Bases of Weighted Outerplanar Graphs, IPL 110:970--974, 2010].

@inproceedings{Doerr2013,
  author = {C. Doerr and G. Ramakrishna and J. M. Schmidt},
  title = {Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time},
  booktitle = {39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'13)},
  year = {2013},
  series_ = {LNCS},
  volume_ = {8165},
  pages = {225-236},
  doi = {http://dx.doi.org/10.1007/978-3-642-45043-3_20}
}
A. Elmasry, K. Mehlhorn and J. M. Schmidt. Every DFS tree of a 3-connected graph contains a contractible edge. Journal of Graph Theory, 72(1):112-121, 2013.
Abstract: Tutte proved that every 3-connected graph G on more than 4 vertices contains a contractible edge. We strengthen this result by showing that every depth-first-search tree of G contains a contractible edge. Moreover, we show that every spanning tree of G contains a contractible edge if G is 3-regular or if G does not contain two disjoint pairs of adjacent degree-3 vertices.
@article{Elmasry2013,
  author = {A. Elmasry and K. Mehlhorn and J. M. Schmidt},
  title = {Every {DFS} tree of a 3-connected graph contains a contractible edge},
  journal = {Journal of Graph Theory},
  year = {2013},
  volume = {72},
  number = {1},
  pages = {112-121},
  doi = {http://dx.doi.org/10.1002/jgt.21635}
}
K. Mehlhorn, A. Neumann and J. M. Schmidt. Certifying 3-Edge-Connectivity. In 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'13), pages 358-369, 2013.
Abstract: We present a linear time certifying algorithm that tests graphs for 3-edge-connectivity. If the input graph G is not 3-edge-connected, the algorithm returns a 2-edge-cut. If G is 3-edge-connected, the algorithm returns a construction sequence that constructs G from the graph with two nodes and three parallel edges using only operations that preserve 3-edge-connectivity. No previous algorithm returned a certificate in the case of a 3-edge-connected input graph.
@inproceedings{Mehlhorn2013,
  author = {K. Mehlhorn and A. Neumann and J. M. Schmidt},
  title = {Certifying 3-Edge-Connectivity},
  booktitle = {39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'13)},
  year = {2013},
  series_ = {LNCS},
  volume_ = {8165},
  pages = {358-369},
  doi = {http://dx.doi.org/10.1007/978-3-642-45043-3_31}
}
J. M. Schmidt. Contractions, Removals and Certifying 3-Connectivity in Linear Time. SIAM Journal on Computing, 42(2):494-535, 2013.
Abstract: One of the most noted construction methods of 3-vertex-connected graphs is due to Tutte and based on the following fact: Any 3-vertex-connected graph G=(V,E) on more than 4 vertices contains a contractible edge, i.e., an edge whose contraction generates a 3-connected graph. This implies the existence of a sequence of edge contractions from G to the complete graph K_4, such that every intermediate graph is 3-vertex-connected. A theorem of Barnette and Grünbaum gives a similar sequence using removals on edges instead of contractions.

We show how to compute both sequences in optimal time, improving the previously best known running times of O(|V|^2) to O(|E|). This result has a number of consequences; an important one is a new linear-time test of 3-connectivity that is certifying; finding such an algorithm has been a major open problem in the design of certifying algorithms in the last years. The test is conceptually different from well-known linear-time 3-connectivity tests and uses a certificate that is easy to verify in time O(|E|). We show how to extend the results to an optimal certifying test of 3-edge-connectivity.

@article{Schmidt2013,
  author = {J. M. Schmidt},
  title = {Contractions, Removals and Certifying 3-Connectivity in Linear Time},
  journal = {SIAM Journal on Computing},
  year = {2013},
  volume = {42(2)},
  pages = {494-535},
  doi = {http://dx.doi.org/10.1137/110848311}
}
J. M. Schmidt. A Simple Test on 2-Vertex- and 2-Edge-Connectivity. Information Processing Letters, 113(7):241-244, 2013.
Abstract: Testing a graph on 2-vertex- and 2-edge-connectivity are two fundamental algorithmic graph problems. For both problems, different linear-time algorithms with simple implementations are known. Here, an even simpler linear-time algorithm is presented that computes a structure from which both the 2-vertex- and 2-edge-connectivity of a graph can be easily ``read off''. The algorithm computes all bridges and cut vertices of the input graph in the same time.
@article{Schmidt2013a,
  author = {J. M. Schmidt},
  title = {A Simple Test on 2-Vertex- and 2-Edge-Connectivity},
  journal = {Information Processing Letters},
  year = {2013},
  volume = {113},
  number = {7},
  pages = {241-244},
  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 765-776, 2013.
Abstract: Linear-time algorithms for testing the planarity of a graph are well known for over 35 years. However, these algorithms are quite involved and recent publications still try to give simpler linear-time tests. We give a conceptually simple reduction from planarity testing to the problem of computing a certain construction of a 3-connected graph. This implies a linear-time planarity test. Our approach is radically different from all previous linear-time planarity tests; as key concept, we maintain a planar embedding that is 3-connected at each point in time. The algorithm computes a planar embedding if the input graph is planar and a Kuratowski-subdivision otherwise.
@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 = {765-776},
  doi = {http://dx.doi.org/10.1007/978-3-642-40313-2_67}
}
A. Elmasry, K. Mehlhorn and J. M. Schmidt. An O(n+m) Certifying Triconnnectivity Algorithm for Hamiltonian Graphs. Algorithmica, 62(3):754-766, 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 = {754-766},
  doi = {http://dx.doi.org/10.1007/s00453-010-9481-2}
}
C. Knauer, L. Schlipf, J. M. Schmidt and H. R. Tiwary. Largest Inscribed Rectangles in Convex Polygons. Journal of Discrete Algorithms, 13:78-85, 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 (1-epsilon) 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 (1-epsilon) 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 = {78-85},
  doi = {http://dx.doi.org/10.1016/j.jda.2012.01.002}
}
J. M. Schmidt. Construction Sequences and Certifying 3-Connectivity. Algorithmica, 62:192-208, 2012.
Abstract: Tutte proved that every 3-vertex-connected graph G on more than 4 vertices has a contractible edge. Barnette and Grünbaum proved the existence of a removable edge in the same setting. We show that the sequence of contractions and the sequence of removals from G to K_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 3-vertex-connectivity of graphs that can be easily computed and verified.
@article{Schmidt2012,
  author = {J. M. Schmidt},
  title = {Construction Sequences and Certifying 3-Connectivity},
  journal = {Algorithmica},
  year = {2012},
  volume = {62},
  pages = {192-208},
  doi = {http://dx.doi.org/10.1007/s00453-010-9450-9}
}
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 201-208, 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 straight-line graph on P. No polynomial-time algorithm is known for this problem. Based on a reduction to the existence of certain diagonals of the boundary cycle of the convex hull of P, we give the first polynomial-time algorithm; the algorithm is constructive and runs in time O(n^3). We also show which graph structure can be expected when there is a cubic plane graph on P; e.g., if P admits a 2-connected cubic plane graph, we show that P admits also a 2-connected cubic plane graph that contains the boundary cycle of P. The algorithm extends to checking P on admitting a 2-connected cubic plane graph.
@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 = {201-208},
  doi = {http://dx.doi.org/10.1145/2261250.2261281},
  isbn = {978-1-4503-1299-8}
}
J. M. Schmidt. Certifying 3-Connectivity in Linear Time. In Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP'12), pages 786-797, 2012.
Abstract: One of the most noted construction methods of 3-vertex-connected graphs is due to Tutte and based on the following fact: Every 3-vertex-connected graph G on more than 4 vertices contains a contractible edge, i.e., an edge whose contraction generates a 3-connected graph. This implies the existence of a sequence of edge contractions from G to K_4 such that every intermediate graph is 3-vertex-connected. A theorem of Barnette and Grünbaum yields a similar sequence using removals 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 linear-time test of 3-connectivity that is certifying; finding such an algorithm has been a major open problem in the design of certifying algorithms in the last years. The 3-connectivity test is conceptually different from well-known linear-time tests on 3-connectivity; 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 3-edge-connectivity.

@inproceedings{Schmidt2012b,
  author = {J. M. Schmidt},
  title = {Certifying 3-Connectivity in Linear Time},
  booktitle = {Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP'12)},
  year = {2012},
  series_ = {LNCS},
  volume_ = {7391},
  pages = {786-797},
  doi = {http://dx.doi.org/10.1007/978-3-642-31594-7_66}
}
J. M. Schmidt. Structure and Constructions of 3-Connected Graphs. Ph.D. Thesis. Freie Universität Berlin, Germany, 2011.
Abstract: The class of 3-connected (i.e. 3-vertex-connected) graphs has been studied intensively for many reasons in the past 50 years. One algorithmic reason is that graph problems can often be reduced to handle only 3-connected graphs; applications include problems in graph drawing, problems related to planarity and online problems on planar graphs. It is possible to test a graph on being 3-connected in linear time. However, the linear-time algorithms known are complicated and difficult to implement. For that reason, it is essential to check implementations of these algorithms to be correct. A way to check the correctness of an algorithm for every instance is to make it certifying, i. e., to enhance its output by an easy-to-verify certificate of correctness for that output. However, surprisingly few work has been devoted to find certifying algorithms that test 3-connectivity; in fact, the currently fastest algorithms need quadratic time.

Two classic results in graph theory due to Barnette, Grünbaum and Tutte show that 3-connected graphs can be characterized by the existence of certain inductively defined constructions. We give new variants of these constructions, relate these to already existing ones and show how they can be exploited algorithmically. Our main result is a linear-time certifying algorithm for testing 3-connectivity, which is based on these constructions. This yields also simple certifying algorithms in linear time for 2-connectivity, 2-edge-connectivity and 3-edge-connectivity. We conclude this thesis by a structural result that shows that one of the constructions is preserved when being applied to depth-first trees of the graph only.

@phdthesis{Schmidt2011,
  author = {J. M. Schmidt},
  title = {Structure and Constructions of 3-Connected Graphs},
  school = {Freie Universit\"at Berlin, Germany},
  year = {2011}
}
J. M. Schmidt. Construction Sequences and Certifying 3-Connectedness. In Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science (STACS'10), pages 633-644, 2010.
Abstract: Tutte proved that every 3-connected 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 3-connectedness of graphs that can be easily computed and verified.
@inproceedings{Schmidt2010,
  author = {J. M. Schmidt},
  title = {Construction Sequences and Certifying 3-Connectedness},
  booktitle = {Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science (STACS'10)},
  year = {2010},
  series_ = {LIPIcs},
  volume_ = {5},
  pages = {633-644},
  doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2491},
  issn = {1868-8969},
  isbn = {978-3-939897-16-3}
}
J. M. Schmidt. Interval Stabbing Problems in Small Integer Ranges. In Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC'09), pages 163-172, 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 = {163-172},
  doi = {http://dx.doi.org/10.1007/978-3-642-10631-6_18},
  isbn = {978-3-642-10630-9}
}
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 159-170, 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 non-planarity. Modern planarity testing algorithms allow to extract a single such witness in linear time. We present the first linear time algorithm which is able to extract multiple Kuratowski subdivisions at once. This is of particular interest for, e.g., Branch-and-Cut algorithms which require multiple such subdivisions to generate cut constraints. The algorithm is not only described theoretically, but we also present an experimental study of its implementation.
@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 = {159-170},
  doi = {http://dx.doi.org/10.1007/978-3-540-77537-9_17},
  issn = {0302-9743 (Print) 1611-3349 (Online)},
  isbn = {978-3-540-77536-2}
}
J. M. Schmidt. Effiziente Extraktion von Kuratowski-Teilgraphen. Diploma Thesis. Technische Universität Dortmund, Germany, 2007.
Abstract: Ein Graph ist nach dem Satz von Kuratowski genau dann planar, wenn er keine Kuratowski-Subdivisions 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 Kuratowski-Subdivisions benötigen. Dazu gehören Branch-and-Cut-Algorithmen für einige NP-schwere Probleme, wie beispielsweise die Kreuzungsminimierung oder auch verschiedene Varianten des Maximum Planar Subgraph Problems. Die Kuratowski-Subdivisions ermöglichen dort die Berechnung von zusätzlichen Nebenbedingungen einer LP-Relaxierung. Dabei ist es wünschenswert, dass die Kuratowski-Subdivisions paarweise entweder möglichst viele Kanten gemeinsam haben oder weitgehend kantendisjunkt sind.

In dieser Diplomarbeit wird ein Algorithmus entworfen und analysiert, der mehrere Kuratowski-Subdivisions in linearer Zeit O(n + m + Sum_(K in S) |E(K)|) extrahieren kann, wobei S die Menge der gefundenen Kuratowski-Subdivisions ist. Dieser Algorithmus stellt eine Erweiterung des aktuellen Planaritätstests von Boyer und Myrvold dar und kann zusätzlich so modifiziert werden, dass entweder möglichst ähnliche oder möglichst verschiedene Kuratowski-Subdivisions ausgegeben werden. Die Laufzeit des Algorithmus ist dabei asymptotisch optimal. Aus diesem Algorithmus wird ein zweiter Ansatz entwickelt, der in der Praxis mehr Kuratowski-Subdivisions extrahieren kann, dafü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 = {1864-4503}
}
B. Baranski, T. Bartz-Beielstein, 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. High-order punishment and the evolution of cooperation. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'06), pages 379-380, 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 high-order 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. Bartz--Beielstein 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 = {High-order punishment and the evolution of cooperation},
  booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'06)},
  year = {2006},
  pages = {379-380},
  doi = {http://dx.doi.org/10.1145/1143997.1144065},
  isbn = {1-59593-186-4}
}
B. Baranski, T. Bartz-Beielstein, 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 1224-1231, 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 vice-versa. While kind agents (e.g. those with a cooperative behavior) lose reputation when being in a group, in which defective strategies are more common, agents with defective behavior on the other hand benefit from a group with more cooperative strategies. We demonstrate that group reputation decreases cooperation with the in-group and increases cooperation with the out-group.
@inproceedings{Baranski2006a,
  author = {B. Baranski and T. Bartz--Beielstein 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 = {1224-1231},
  doi = {http://dx.doi.org/10.1109/CEC.2006.1688449}
}

Created on 2017-12-05