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 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). 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.
This research was partly done at Max Planck Institute for Informatics, Saarbrücken.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Badent, M., Brandes, U., Cornelsen, S.: More canonical ordering. J. Graph Algorithms Appl. 15(1), 97–126 (2011)
Barnette, D.W., Grünbaum, B.: On Steinitz’s theorem concerning convex 3-polytopes and on some properties of planar graphs. In: Many Facets of Graph Theory, pp. 27–40 (1969)
Brandes, U.: Eager st-ordering. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 247–256. Springer, Heidelberg (2002)
Cheriyan, J., Maheshwari, S.N.: Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs. J. Algorithms 9(4), 507–537 (1988)
Curran, S., Lee, O., Yu, X.: Finding four independent trees. SIAM Journal on Computing 35(5), 1023–1058 (2006)
de Fraysseix, H., Pach, J., Pollack, R.: Small sets supporting fary embeddings of planar graphs. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC 1988), pp. 426–433 (1988)
de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)
Di Battista, G., Tamassia, R., Vismara, L.: Output-sensitive reporting of disjoint paths. Algorithmica 23(4), 302–340 (1999)
Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM J. Comput. 2(3), 135–158 (1973)
Huck, A.: Independent trees in planar graphs. Graphs and Combinatorics 15(1), 29–77 (1999)
Itai, A., Rodeh, M.: The multi-tree approach to reliability in distributed networks. Information and Computation 79, 43–59 (1988)
Kant, G.: Drawing planar graphs using the lmc-ordering. In: Proceedings of the 33th Annual Symposium on Foundations of Computer Science (FOCS 1992), pp. 101–110 (1992)
Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4–32 (1996)
Lovász, L.: Computing ears and branchings in parallel. In: Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS 1985), pp. 464–467 (1985)
Mondshein, L.F.: Combinatorial Ordering and the Geometric Embedding of Graphs. PhD thesis, M.I.T. Lincoln Laboratory / Harvard University (1971), Technical Report, available at http://www.dtic.mil/cgi-bin/GetTRDoc?AD=AD0732882
Mutzel, P.: The SPQR-tree data structure in graph drawing. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 34–46. Springer, Heidelberg (2003)
Schmidt, J.M.: Contractions, removals and certifying 3-connectivity in linear time. SIAM Journal on Computing 42(2), 494–535 (2013)
Suzuki, H., Takahashi, N., Nishizek, T., Miyano, H., Ueno, S.: An algorithm for tripartitioning 3-connected graphs. Information Processing Society of Japan (IPSJ) 31(5), 584–592 (1990) (in Japanese).
Thomassen, C.: Kuratowski’s theorem. J. Graph Theory 5(3), 225–241 (1981)
Tutte, W.T.: How to draw a graph. Proc. Lond. Math. Soc. 13, 743–767 (1963)
Tutte, W.T.: Connectivity in graphs. In: Mathematical Expositions, vo. 15, University of Toronto Press (1966)
Wada, K., Kawaguchi, K.: Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs. In: van Leeuwen, J. (ed.) WG 1993. LNCS, vol. 790, pp. 132–143. Springer, Heidelberg (1994)
Whitney, H.: Non-separable and planar graphs. Trans. Amer. Math. Soc. 34(1), 339–362 (1932)
Zehavi, A., Itai, A.: Three tree-paths. J. Graph Theory 13(2), 175–188 (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schmidt, J.M. (2014). The Mondshein Sequence. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds) Automata, Languages, and Programming. ICALP 2014. Lecture Notes in Computer Science, vol 8572. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43948-7_80
Download citation
DOI: https://doi.org/10.1007/978-3-662-43948-7_80
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43947-0
Online ISBN: 978-3-662-43948-7
eBook Packages: Computer ScienceComputer Science (R0)