Options
Mondshein sequences (A.K.A. (2; 1)-orders)
Publikationstyp
Journal Article
Date Issued
2016
Sprache
English
Author(s)
TORE-URI
Journal
Volume
45
Issue
6
Start Page
1985
End Page
2003
Citation
SIAM Journal on Computing (2016)
Publisher DOI
Scopus ID
Canonical orderings have been used as a key tool in graph drawing, graph encoding, and visibility representations for the last decades [H. de Fraysseix, J. Pach, and R. Pollack, Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC '88), ACM, New York, 1988, pp. 426-433; G. Kant, Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS '92), IEEE Press, Piscataway, NJ, 1992, pp. 101-110]. We study a far-reaching generalization of canonical orderings to nonplanar graphs that was published by Lee Mondshein in a Ph.D. thesis 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 essentially induce a 2-connected graph, while the remaining vertices from i+1 to n induce a connected graph. Mondshein's sequence generalizes canonical orderings and later became independently known as nonseparating ear decomposition. Surprisingly, this fundamental link between canonical orderings and nonseparating ear decomposition had not been previously established. 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-in four of these, the previous best running time was 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 (1988), pp. 507-537]; improve the preprocessing time from O(n2) to O(m) for the output-sensitive data structure of Di Battista, Tamassia, and Vismara [Algorithmica, 23 (1999), pp. 302-340] that reports three internally disjoint paths between any given vertex pair; derive a very simple O(n)-time planarity test once a Mondshein sequence is computed; compute a nested family of contractible subgraphs of 3-connected graphs in time O(m); and compute a 3-partition in time O(m) (the previous best running time is O(n2) due to Suzuki et al. [Information Processing Society of Japan (IPSJ), 31 (1990), pp. 584-592 (in Japanese)]).
Subjects
(2,1)-order
Canonical ordering
Graph drawing
Independent spanning trees
Monshein sequence
Nonseperating ear decomposition
DDC Class
510: Mathematik