Editing Graph minor (section)

==Algorithms==
The problem of [[decision problem|deciding]] whether a graph ''G'' contains ''H'' as a minor is NP-complete in general; for instance, if ''H'' is a [[cycle graph]] with the same number of vertices as ''G'', then ''H'' is a minor of ''G'' if and only if ''G'' contains a [[Hamiltonian cycle]]. However, when ''G'' is part of the input but ''H'' is fixed, it can be solved in polynomial time. More specifically, the running time for testing whether ''H'' is a minor of ''G'' in this case is ''O''(''n''<sup>3</sup>), where ''n'' is the number of vertices in ''G'' and the [[big O notation]] hides a constant that depends superexponentially on ''H'';<ref name="rs95">{{harvtxt|Robertson|Seymour|1995}}.</ref> since the original Graph Minors result, this algorithm has been improved to ''O''(''n''<sup>2</sup>) time.<ref name="kkr12">{{harvtxt|Kawarabayashi|Kobayashi|Reed|2012}}.</ref> Thus, by applying the polynomial time algorithm for testing whether a given graph contains any of the forbidden minors, it is theoretically possible to recognize the members of any minor-closed family in [[polynomial time]].  This result is not used in practice since the hidden constant is so huge (needing three layers of [[Knuth's up-arrow notation]] to express) as to rule out any application, making it a [[galactic algorithm]].<ref>{{cite journal |author=Johnson, David S. |title=The NP-completeness column: An ongoing guide (edition 19) |journal= Journal of Algorithms |volume=8 |issue=2 |year=1987 |pages=285–303 |citeseerx=10.1.1.114.3864 |doi=10.1016/0196-6774(87)90043-5 }}</ref>  Furthermore, in order to apply this result constructively, it is necessary to know what the forbidden minors of the graph family are.<ref name="fl88">{{harvtxt|Fellows|Langston|1988}}.</ref> In some cases, the forbidden minors are known, or can be computed.<ref>{{Cite journal|last=Bodlaender|first=Hans L.|date=1993|title=A Tourist Guide through Treewidth|url=https://dspace.library.uu.nl/bitstream/handle/1874/2301/1992-12.pdf?sequence=1|journal=Acta Cybernetica|volume=11|pages=1–21}} See end of Section 5.</ref>

In the case where ''H'' is a fixed [[planar graph]], then we can test in linear time in an input graph ''G'' whether ''H'' is a minor of ''G''.<ref>{{Cite journal|last=Bodlaender|first=Hans L.|date=1993|title=A Tourist Guide through Treewidth|url=https://dspace.library.uu.nl/bitstream/handle/1874/2301/1992-12.pdf?sequence=1|journal=Acta Cybernetica|volume=11|pages=1–21}} First paragraph after Theorem 5.3</ref> In cases where ''H'' is not fixed, faster algorithms are known in the case where ''G'' is planar.<ref>{{Cite journal|last1=Adler|first1=Isolde|last2=Dorn|first2=Frederic|last3=Fomin|first3=Fedor V.|last4=Sau|first4=Ignasi|last5=Thilikos|first5=Dimitrios M.|date=2012-09-01|title=Fast Minor Testing in Planar Graphs|url=http://www.lirmm.fr/~sau/Pubs/Minor-planar.pdf|journal=Algorithmica|language=en|volume=64|issue=1|pages=69–84|doi=10.1007/s00453-011-9563-9|s2cid=6204674|issn=0178-4617}}</ref>