Document Open Access Logo

Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs

Authors Frank Kammer, Dieter Kratsch, Moritz Laudahn

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.56.pdf
  • Filesize: 406 kB
  • 14 pages

Document Identifiers

Author Details

Frank Kammer
Dieter Kratsch
Moritz Laudahn

Cite As Get BibTex

Frank Kammer, Dieter Kratsch, and Moritz Laudahn. Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.56

Abstract

We present space-efficient algorithms for computing cut vertices in   a given graph with n vertices and m edges in linear time using O(n+min{m,n log log n}) bits. With the same time and using O(n+m) bits, we can compute the biconnected components of a graph. We use this result to show an algorithm for the recognition of (maximal) outerplanar graphs in O(n log log n) time using O(n) bits.

Subject Classification

Keywords
  • graph algorithms
  • space efficiency
  • cut vertices
  • maximal outerplanar graphs

Metrics

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

References

  1. Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote, and André Schulz. Reprint of: Memory-constrained algorithms for simple polygons. Comput. Geom. Theory Appl., 47(3, Part B):469-479, 2014. URL: http://dx.doi.org/10.1016/j.comgeo.2013.11.004.
  2. Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, and Ryuhei Uehara. Depth-first search using O(n) bits. In Proc. 25th International Symposium on Algorithms and Computation (ISAAC 2014), volume 8889 of LNCS, pages 553-564. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-13075-0_44.
  3. Tetsuo Asano, Wolfgang Mulzer, Günter Rote, and Yajun Wang. Constant-work-space algorithms for geometric problems. J. Comput. Geom., 2(1):46-68, 2011. Google Scholar
  4. Luis Barba, Matias Korman, Stefan Langerman, Rodrigo I. Silveira, and Kunihiko Sadakane. Space-time trade-offs for stack-based algorithms. In Proc. 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), volume 20 of LIPIcs, pages 281-292. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2013.281.
  5. Paul Beame. A general sequential time-space tradeoff for finding unique elements. SIAM J. Comput., 20(2):270-277, 1991. URL: http://dx.doi.org/10.1137/0220017.
  6. A. Brandstädt, V. Le, and J. Spinrad. Graph Classes: A Survey. Society for Industrial and Applied Mathematics, 1999. URL: http://dx.doi.org/10.1137/1.9780898719796.
  7. David Clark. Compact Pat Trees. PhD thesis, University of Waterloo, Waterloo, Ontario, Canada, 1996. Google Scholar
  8. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 3rd edition, 2009. Google Scholar
  9. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  10. Jeff Edmonds, Chung Keung Poon, and Dimitris Achlioptas. Tight lower bounds for st-connectivity on the NNJAG model. SIAM J. Comput., 28(6):2257-2284, 1999. URL: http://dx.doi.org/10.1137/S0097539795295948.
  11. Amr Elmasry, Torben Hagerup, and Frank Kammer. Space-efficient basic graph algorithms. In Proc. 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume 30 of LIPIcs, pages 288-301. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.288.
  12. Torben Hagerup and Frank Kammer. Succinct choice dictionaries. Computing Research Repository (CoRR), arXiv:1604.06058 [cs.DS], 2016. Google Scholar
  13. Torben Hagerup, Frank Kammer, and Moritz Laudahn. Space-efficient euler partition and bipartite edge coloring. Talk given on the theory days of computer science of the Gesellschaft für Informatik in Speyer, Germany, 2015. Google Scholar
  14. Frank Kammer, Dieter Kratsch, and Moritz Laudahn. Space-efficient biconnected components and recognition of outerplanar graphs. Computing Research Repository (CoRR), arXiv:1606.04679 [cs.DS], 2016. Google Scholar
  15. Sandra L. Mitchell. Linear algorithms to recognize outerplanar and maximal outerplanar graphs. Inf. Process. Lett., 9(5):229-232, 1979. URL: http://dx.doi.org/10.1016/0020-0190(79)90075-9.
  16. J. I. Munro and M. S. Paterson. Selection and sorting with limited storage. Theor. Comput. Sci., 12(3):315-323, 1980. URL: http://dx.doi.org/10.1016/0304-3975(80)90061-4.
  17. Jakob Pagter and Theis Rauhe. Optimal time-space trade-offs for sorting. In Proc. 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1998), pages 264-268. IEEE Computer Society, 1998. URL: http://dx.doi.org/10.1109/SFCS.1998.743455.
  18. Omer Reingold. Undirected connectivity in log-space. J. ACM, 55(4):17:1-17:24, September 2008. URL: http://dx.doi.org/10.1145/1391289.1391291.
  19. Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci., 4(2):177-192, 1970. URL: http://dx.doi.org/10.1016/S0022-0000(70)80006-X.
  20. Robert Endre Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1(2):146-160, 1972. URL: http://dx.doi.org/10.1137/0201010.
  21. Manfred Wiegers. Recognizing outerplanar graphs in linear time. In Proc. International Workshop on Graphtheoretic Concepts in Computer Science (WG 1986), volume 246 of LNCS, pages 165-176. Springer, 1986. URL: http://dx.doi.org/10.1007/3-540-17218-1_57.
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