AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

We study a long-forgotten 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.

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$. From this result, we deduce linear-time algorithms for several other problems, for which the previous best running times have been quadratic.

Jens M. Schmidt

--email hidden

passcode not visible

logged in users only