Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Edge separators for planar graphs and their applications

  • Communications
  • Conference paper
  • First Online:
Mathematical Foundations of Computer Science 1988 (MFCS 1988)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 324))

Abstract

We show that every planar graph with n vertices and a maximal degree k has an 0(√kn)-edge separator. This improves known results about edge separators of graphs with vertex degree bounded by a constant. We show that any n vertex tree of a maximal degree k can be divided into two parts of ≤ n / 2 vertices by removing 0(klog n/log k) edges. The sizes of both separators are existentially optimal. We apply the edge separator to average cost efficient embeddings of planar graphs of degree k into binary trees, meshes and hypercubes.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. F. Berman, L. Snyder, On mapping parallel algorithms into parallel architectures, J. of Parallel and Distributed Computing, Vol.4, 1987, pp. 439–458.

    Google Scholar 

  2. H.N. Djidjev, On the problem of partitioning planar graphs, SIAM J. Alg. Disc. Meth., Vol. 3, No. 2, 1982, pp.229–240.

    Google Scholar 

  3. H.N. Djidjev, A Linear algorithm for partitioning graphs of fixed genus, SERDICA, Vol. 11, 1985, 369–387.

    Google Scholar 

  4. H.N. Djidjev, A separator theorem for graphs of fixed genus, SERDICA, Vol. 11, 1985, pp. 319–329.

    Google Scholar 

  5. R.A. De Millo, S.C. Eisenstat, R.J.L. Lipton, Preserving average proximity in arrays, Comm. ACM, 21, 1978, pp. 228–230.

    Google Scholar 

  6. H.Gazit, An improved algorithm for separating planar graphs, manuscript.

    Google Scholar 

  7. J.R.Gilbert, J.P.Hutchinson, R.E.Tarjan, A separator theorem for graphs of bounded genus, Journal of Algorithsm, No.5, 1984, pp. 391–398.

    Google Scholar 

  8. J.R.Gilbert, Graph separator theorem and sparse Gaussian elimination, Ph.D. thesis, Stanford University, 1980.

    Google Scholar 

  9. H.Gazit, G.L.Miller, A parallel algorithm for finding a separator for planar graphs. In: Proc. 28-th. Foundations of Computer Science, IEEE, 1987, 238–248.

    Google Scholar 

  10. L.S. Heath, Embedding outerplanar graphs in small books, SIAM J. Alg. Disc. Meth., Vol.8, No.2, 1987, pp. 198–218.

    Google Scholar 

  11. J. Hong, A.L. Rosenberg, Graphs that are almost binary trees, SIAM J. Comput., Vol. 11, No. 2, 1982, pp. 227–242.

    Google Scholar 

  12. M.A. Jordanskij, Minimal numberings of tree vertices, Probl. Kib., Vol. 31, 1976, pp.109–133 (in Russian).

    Google Scholar 

  13. D.B. Johnson, S.M. Venkatesan, Partition of planar flows in networks. In: Proc. 24-th Ann. Symp. on Theory of Computing, ACM, New York, 1983, pp. 259–263.

    Google Scholar 

  14. R.J. Lipton, D.J. Rose, R.E. Tarjan, Generalized nested dissection, SIAM J. Numer. Anal., 16, 1979, 346–358.

    Google Scholar 

  15. C.E.Leiserson, Area efficient graph layout (for VLSI), In: Proc. 21-st Foundations of Computer Science, IEEE, Syracuse, 1980, pp. 270–281.

    Google Scholar 

  16. F.T. Leighton, A layout strategy which is provably good, In: Proc. 23-rd Foundations of Computer Science, IEEE, San Francisco, 1982, pp. 85–98.

    Google Scholar 

  17. R.J. Lipton, R.E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math., Vol. 36, No. 2, 1979, pp. 177–189.

    Google Scholar 

  18. R.J. Lipton, R.E. Tarjan, Applications of a planar separator theorem, SIAM J. Computing, Vol. 9, No.3, 1980, pp. 615–627.

    Google Scholar 

  19. G.L. Miller, Finding small simple cycle-separators for 2-connected planar graphs, J. of Comp. and System Science, Vol. 32, 1986, pp. 265–279.

    Google Scholar 

  20. B.Monien, The complexity of embedding graphs into binary trees, In: FCTo 85, LNCS 199, pp. 300–309.

    Google Scholar 

  21. S. Mitchel, Linear algorithm to recognize outerplanar and maximal outerplanar graphs, IPL, Vol. 9, No.5, 1979, pp.229–232.

    Google Scholar 

  22. S.Rao, Finding near optimal separators in planar graphs, In: Proc. 28-th Foundations of Computer Science. IEEE, 1987, pp. 225–237.

    Google Scholar 

  23. S.S. Ravi, H.B. Hunt, An application of the planar separator theorem to counting problem, IPL, Vol. 25, No.6, 1987, pp.317–322.

    Google Scholar 

  24. D. Richards, Finding short cycles in planar graphs using separators, J. of Algorithms, Vol. 7, 1986, pp. 382–394.

    Google Scholar 

  25. A.L. Rosenberg, A hypergraph model for fault-tolerant VLSI processor arrays, IEEE Trans. on Computers, C-34, No. 6, 1985, pp. 578–584.

    Google Scholar 

  26. M.A. Scheidwasser, On the length and the width of embeddings of graphs in meshes, Probl. Kib., Vol. 29, 1974, pp.63–102 (in Russian).

    Google Scholar 

  27. J.G. Valiant, Universality consideration in VLSI circuits, IEEE Trans. on Computers, C-30, No.2, 1981, pp. 135–140.

    Google Scholar 

  28. S.M.Venkatesan, Improved constants for some separator theorems, J. of Algorithms, to appear.

    Google Scholar 

  29. S.M.Venkatesan, On separating a planar graph into two halves, Submitted to SIAM J. of Discrete Mathematics.

    Google Scholar 

  30. M. Yannakakis, Linear and book embeddings of graphs, in: Proc. Aegean Workshop on Computing, July 8–11, 1986, Lecture Notes in Computer Science, Vol. 227, Springer-Verlag, Berlin, 1986.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Informatics, Warsaw University, PKiN, 00901, Warsaw, Poland

    Krzystof Diks

  2. Centre of Informatics and Computer Technology, Bulgarian Academy of Sciences, Acad. Bonchev str. bl. 25-A, 1113, Sofia, Bulgaria

    Hristo N. Djidjev

  3. Institute of Technical Cybernetics, Slovak Academy of Sciences, Dúbravská 9, 842 37, Bratislava, Czechoslovakia

    Ondrej Sykora & Imrich Vrto

Authors
  1. Krzystof Diks
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hristo N. Djidjev
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ondrej Sykora
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Imrich Vrto
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Michal P. Chytil Václav Koubek Ladislav Janiga

Rights and permissions

Reprints and permissions

Copyright information

© 1988 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Diks, K., Djidjev, H.N., Sykora, O., Vrto, I. (1988). Edge separators for planar graphs and their applications. In: Chytil, M.P., Koubek, V., Janiga, L. (eds) Mathematical Foundations of Computer Science 1988. MFCS 1988. Lecture Notes in Computer Science, vol 324. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0017151

Download citation

  • DOI: https://doi.org/10.1007/BFb0017151

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-50110-7

  • Online ISBN: 978-3-540-45926-2

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation