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 (n 2) 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
Link To Document