Document Open Access Logo

Edge-Orders

Authors Lena Schlipf, Jens M. Schmidt

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.75.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Lena Schlipf
Jens M. Schmidt

Cite As Get BibTex

Lena Schlipf and Jens M. Schmidt. Edge-Orders. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 75:1-75:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.75

Abstract

Canonical orderings and their relatives such as st-numberings have been used as a key tool in algorithmic graph theory for the last decades. Recently, a unifying link behind all these orders has been shown that links them to well-known graph decompositions into parts that have a prescribed vertex-connectivity.

Despite extensive interest in canonical orderings, no analogue of this unifying concept is known for edge-connectivity. In this paper, we establish such a concept named edge-orders and show how to compute (1,1)-edge-orders of 2-edge-connected graphs as well as (2,1)-edge-orders of 3-edge-connected graphs in linear time, respectively. While the former can be seen as the edge-variants of st-numberings, the latter are the edge-variants of Mondshein sequences and non-separating ear decompositions. The methods that we use for obtaining such edge-orders differ considerably in almost all details from the ones used for their vertex-counterparts, as different graph-theoretic constructions are used in the inductive proof and standard reductions from edge- to vertex-connectivity are bound to fail.

As a first application, we consider the famous Edge-Independent Spanning Tree Conjecture, which asserts that every k-edge-connected graph contains k rooted spanning trees that are pairwise edge-independent. We illustrate the impact of the above edge-orders by deducing algorithms that construct 2- and 3-edge independent spanning trees of 2- and 3-edge-connected graphs, the latter of which improves the best known running time from O(n^2) to linear time.

Subject Classification

Keywords
  • edge-order
  • st-edge-order
  • canonical ordering
  • edge-independent spanning tree
  • Mondshein sequence
  • linear time

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Fred Annexstein, Ken Berman, and Ram Swaminathan. Independent spanning trees with small stretch factors. Technical Report 96-13, DIMACS, June 1996. Google Scholar
  2. M. Badent, U. Brandes, and S. Cornelsen. More canonical ordering. Journal of Graph Algorithms and Applications, 15(1):97-126, 2011. Google Scholar
  3. M. A. Bender, R. Cole, E. D. Demaine, M. Farach-Colton, and J. Zito. Two simplified algorithms for maintaining order in a list. In Proceedings of the 10th European Symposium on Algorithms (ESA'02), pages 152-164, 2002. URL: http://dx.doi.org/10.1007/3-540-45749-6_17.
  4. T. Biedl and M. Derka. The (3,1)-ordering for 4-connected planar triangulations. Journal of Graph Algorithms and Applications, 20(2):347-362, 2016. Google Scholar
  5. T. Biedl and J. M. Schmidt. Small-area orthogonal drawings of 3-connected graphs. In Proceedings of the 23rd International Symposium on Graph Drawing (GD'15), pages 153-165, 2015. URL: http://dx.doi.org/10.1007/978-3-319-27261-0_13.
  6. J. Cheriyan and S. N. Maheshwari. Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs. Journal of Algorithms, 9(4):507-537, 1988. Google Scholar
  7. S. Curran, O. Lee, and X. Yu. Chain decompositions of 4-connected graphs. SIAM J. Discrete Math., 19(4):848-880, 2005. URL: http://dx.doi.org/10.1137/S0895480103434592.
  8. H. de Fraysseix, J. Pach, and R. Pollack. Small sets supporting fary embeddings of planar graphs. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC'88), pages 426-433, 1988. URL: http://dx.doi.org/10.1145/62212.62254.
  9. S. Even and R. E. Tarjan. Computing an st-Numbering. Theor. Comput. Sci., 2(3):339-344, 1976. Google Scholar
  10. Z. Galil and G. F. Italiano. Reducing edge connectivity to vertex connectivity. SIGACT News, 22(1):57-61, 1991. URL: http://dx.doi.org/10.1145/122413.122416.
  11. A. Gopalan and S. Ramasubramanian. On constructing three edge independent spanning trees. Manuscript (see http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.406.7119), March 2011.
  12. A. Gopalan and S. Ramasubramanian. A counterexample for the proof of implication conjecture on independent spanning trees. Information Processing Letters, 113(14-16):522-526, 2013. URL: http://dx.doi.org/10.1016/j.ipl.2013.04.008.
  13. A. Itai and M. Rodeh. The multi-tree approach to reliability in distributed networks. Information and Computation, 79:43-59, 1988. Google Scholar
  14. G. Kant. Drawing planar graphs using the lmc-ordering. In Proceedings of the 33th Annual Symposium on Foundations of Computer Science (FOCS'92), pages 101-110, 1992. URL: http://dx.doi.org/10.1109/SFCS.1992.267814.
  15. L. Lovász. Computing ears and branchings in parallel. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS'85), pages 464-467, 1985. URL: http://dx.doi.org/10.1109/SFCS.1985.16.
  16. W. Mader. A reduction method for edge-connectivity in graphs. In B. Bollobás, editor, Advances in Graph Theory, volume 3 of Annals of Discrete Mathematics, pages 145-164. North-Holland, 1978. URL: http://dx.doi.org/10.1016/S0167-5060(08)70504-1.
  17. R. M. McConnell, K. Mehlhorn, S. Näher, and P. Schweitzer. Certifying algorithms. Computer Science Review, 5(2):119-161, 2011. URL: https://doi.org/10.1016/j.cosrev.2010.09.009.
  18. K. Mehlhorn, A. Neumann, and J. M. Schmidt. Certifying 3-edge-connectivity. Algorithmica, 77(2):309-335, 2017. URL: http://dx.doi.org/10.1007/s00453-015-0075-x.
  19. L. F. Mondshein. Combinatorial Ordering and the Geometric Embedding of Graphs. PhD thesis, M.I.T. Lincoln Laboratory / Harvard University, 1971. Technical Report available at URL: http://www.dtic.mil/cgi-bin/GetTRDoc?AD=AD0732882.
  20. S. Nagai and S. Nakano. A linear-time algorithm to find independent spanning trees in maximal planar graphs. In 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'00), pages 290-301, 2000. URL: http://dx.doi.org/10.1007/3-540-40064-8_27.
  21. S. Nakano, Md. S. Rahman, and T. Nishizeki. A linear-time algorithm for four-partitioning four-connected planar graphs. Inf. Process. Lett., 62(6):315-322, 1997. URL: http://dx.doi.org/10.1016/S0020-0190(97)00083-5.
  22. H. E. Robbins. A theorem on graphs, with an application to a problem of traffic control. The American Mathematical Monthly, 46(5):281-283, 1939. URL: http://www.jstor.org/stable/2303897.
  23. J. M. Schmidt. Construction sequences and certifying 3-connectedness. In Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science (STACS'10), pages 633-644, 2010. URL: http://arxiv.org/abs/0912.2561, URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2491.
  24. J. M. Schmidt. A simple test on 2-vertex- and 2-edge-connectivity. Information Processing Letters, 113(7):241-244, 2013. URL: http://dx.doi.org/10.1016/j.ipl.2013.01.016.
  25. J. M. Schmidt. The Mondshein sequence. In Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14), pages 967-978, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_80.
  26. J. M. Schmidt. Mondshein sequences (a.k.a. (2,1)-orders). SIAM Journal on Computing, 45(6):1985-2003, 2016. URL: http://dx.doi.org/10.1137/15M1030030.
  27. K. Wada and K. Kawaguchi. Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs. In 19th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'93), pages 132-143, 1993. URL: http://dx.doi.org/10.1007/3-540-57899-4_47.
  28. K. Wada, A. Takaki, and K. Kawaguchi. Efficient algorithms for a mixed k-partition problem of graphs without specifying bases. Theoretical Computer Science, 201:233-248, 1998. Google Scholar
  29. H. Whitney. Non-separable and planar graphs. Transactions of the American Mathematical Society, 34(1):339-362, 1932. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact