Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Drawing Planar Graphs Read chapter Read first chapter

2020 | OriginalPaper | Chapter

Space Efficient Separator Algorithms for Planar Graphs

Author : Osamu Watanabe

Published in: WALCOM: Algorithms and Computation

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The Separator Theorem states that any planar graph G with n vertices has a separator of size \(O(\sqrt{n})\), that is, a set S of \(O(\sqrt{n})\) vertices of G such that by removing S, G is split into disconnected subgraphs of almost equal size, say, each having more than n/3 vertices. A separator algorithm is an algorithm that computes a separator for a given planar graph. We consider two algorithms that have been developed recently by the author and his colleagues [4, 6] for designing a “sublinear-space” and polynomial-time separator algorithm.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Drawing Planar Graphs
next chapter Recent Progresses in the Combinatorial and Algorithmic Study of Rooted Phylogenetic Networks
Literature
1.
2.
Asano, T., Doerr, B.: Memory-constrained algorithms for shortest path problem. In: Proceedings of the 23rd CCCG (2011)
3.
Asano, T., Kirkpatrick, D., Nakagawa, K., Watanabe, O.: \(\widetilde{O}(\sqrt{n})\)-Space and polynomial-time algorithm for planar directed graph reachability. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014. LNCS, vol. 8635, pp. 45–56. Springer, Heidelberg (2014). https://​doi.​org/​10.​1007/​978-3-662-44465-8_​5CrossRef
4.
Ashida, R., Kuhnert, S., Watanabe, O.: A space-efficient separator algorithm for planar graphs. IEICE Trans. Fundam. E102–A(9), 1007–1016 (2019). A version with a simplified proof is available from Tokyo Tech Research Repository, search “T2R2 Osamu Watanabe.”CrossRef
5.
Ashida, R., Nakagawa, K.: \(\widetilde{O}\)\((n^{1/3})\)–space algorithm for the grid graph reachability problem. In: Proceedings of the 34th SoCG, pp. 5:1–5:13 (2018)
6.
Ashida, R., Imai, T., Nakagawa, K., Pavan, A., Vinodchandran, N.V., Watanabe, O.: A sublinear-space and polynomial-time separator algorithm for planar graphs. Electron. Colloquium Comput. Complex. (ECCC) 26(91) (2019)
7.
Barnes, G., Buss, J.F., Ruzzo, W.L., Schieber, B.: A sublinear space, polynomial time algorithm for directed s-t connectivity. In: Proceedings Structure in Complexity Theory Conference, pp. 27–33. IEEE (1992)
8.
Gazit, H., Miller, G.L.: A parallel algorithm for finding a separator in planer graphs. In: Proceedings of the 28th FOCS, pp. 238–248 (1987)
9.
Imai, T., Nakagawa, K., Pavan, A., Vinodchandran, N.V., Watanabe, O.: An \(O({n^{{1\over 2}+\epsilon }})\)-space and polynomial-time algorithm for directed planar reachability. In: Proceedings of the 28th CCC, pp. 277–286 (2013)
10.
Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. J. Comput. Syst. Sci. 32(3), 265–279 (1986)MathSciNetCrossRef
11.
12.
Metadata
Title
Space Efficient Separator Algorithms for Planar Graphs
Author
Osamu Watanabe
Copyright Year
2020
Book
WALCOM: Algorithms and Computation

Print ISBN: 978-3-030-39880-4

Electronic ISBN: 978-3-030-39881-1

Copyright Year: 2020

DOI
https://doi.org/10.1007/978-3-030-39881-1_2

Premium Partner

    Image Credits