• DocumentCode
    2893026
  • Title

    Computing planar intertwines

  • Author

    Gupta, Arvind ; Impagliazzo, Russell

  • Author_Institution
    Sch. of Comput. Sci., Simon Fraser Univ., Burnaby, BC, Canada
  • fYear
    1991
  • fDate
    1-4 Oct 1991
  • Firstpage
    802
  • Lastpage
    811
  • Abstract
    The proof of Wagner´s conjecture by N. Robertson and P. Seymour gives a finite description of any family of graphs which is closed under the minor ordering, called the obstructions of the family. Since the intersection and the union of two minor closed graph families are again a minor closed graph family, an interesting question is that of computing the obstructions of the new family given the obstructions for the original two families. It is easy to compute the obstructions of the intersection, but, until very recently, it was an open problem to compute the obstructions of the union. It is shown that if the original families are planar, then the obstructions of the union are no larger than n to the O(n2) power, where n is the size of the largest obstruction of the original family
  • Keywords
    computational complexity; graph theory; graph family obstructions; minor closed graph families; minor ordering; planar intertwines; Combinatorial mathematics; Computer science; Embedded computing; Polynomials; Testing; Upper bound;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
  • Conference_Location
    San Juan
  • Print_ISBN
    0-8186-2445-0
  • Type

    conf

  • DOI
    10.1109/SFCS.1991.185452
  • Filename
    185452