  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 of a 3-connected graph
in time O(m), - improve the preprocessing time from O(n^2) to O(m) for a data
structure reporting 3 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).
