Item

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 \emph{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.