• DocumentCode
    2178585
  • Title

    Applications of a planar separator theorem

  • Author

    Lipton, Hichard J. ; Tarjan, Robert Endre

  • fYear
    1977
  • fDate
    Oct. 31 1977-Nov. 2 1977
  • Firstpage
    162
  • Lastpage
    170
  • Abstract
    Any n-vertex planar graph has the property that it can be divided into components of roughly equal size by removing only O(√n) vertices. This separator theorem, in combination with a divide-and-conquer strategy, leads to many new complexity results for planar graph problems. This paper describes some of these results.
  • Keywords
    Application software; Approximation algorithms; Circuits; Complexity theory; Computer science; Costs; Dynamic programming; NP-complete problem; Particle separators;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1977., 18th Annual Symposium on
  • Conference_Location
    Providence, RI, USA
  • ISSN
    0272-5428
  • Type

    conf

  • DOI
    10.1109/SFCS.1977.6
  • Filename
    4567938
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2178585