Options
The Mondshein sequence
Publikationstyp
Conference Paper
Date Issued
2014
Sprache
English
Author(s)
TORE-URI
First published in
Number in series
8572 LNCS
Issue
PART 1
Start Page
967
End Page
978
Citation
International Colloquium on Automata, Languages, and Programming (ICALP 2014)
Publisher DOI
Scopus ID
Publisher
Springer
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(n2) to O(m). Thirdly, we improve the computation of 3-partitioning of a 3-connected graph to linear time. Finally, we show how a very simple linear-time planarity test can be derived once a Mondshein sequence is computed.
DDC Class
510: Mathematik