Content deleted Content added
Added free to read link in citations with OAbot #oabot |
|||
Line 54:
''O''(''n''<sup>''O''(''g'')</sup>) were independently submitted to the Annual [[ACM Symposium on Theory of Computing]]: one by I. Filotti and [[Gary Miller (computer scientist)|G.L. Miller]] and another one by [[John Reif]]. Their approaches were quite different, but upon the suggestion of the program committee they presented a joint paper.<ref>{{citation|first1=I. S.|last1=Filotti|author2-link=Gary Miller (computer scientist)|first2=Gary L.|last2=Miller|first3=John|last3=Reif|author3-link=John Reif |title=[[Symposium on Theory of Computing|Proc. 11th Annu. ACM Symposium on Theory of Computing]]|year=1979|pages=27–37|doi=10.1145/800135.804395|chapter=On determining the genus of a graph in O(v O(g)) steps(Preliminary Report)}}.</ref> However, Myrvold and Kocay proved in 2011 that the algorithm given by Filotti, Miller and Reif was incorrect<ref>{{cite journal|last1=Myrvold|first1=Wendy|last2=Kocay|first2=William|title=Errors in Graph Embedding Algorithms|journal=Journal of Computer and System Sciences|date=March 1, 2011|volume=2|issue=77|page=430-438|doi=10.1016/j.jcss.2010.06.002|url=https://www.sciencedirect.com/science/article/pii/S0022000010000863}}</ref>.
In 1999 it was reported that the fixed-genus case can be solved in time [[linear time|linear]] in the graph size and [[Double exponential function|doubly exponential]] in the genus.<ref>{{Citation | last1=Mohar | first1=Bojan | authorlink = Bojan Mohar | title=A linear time algorithm for embedding graphs in an arbitrary surface | year=1999 | journal=[[SIAM Journal on Discrete Mathematics]] | volume=12 | issue=1 | pages=6–26 | doi = 10.1137/S089548019529248X| citeseerx=10.1.1.97.9588 }}</ref>
==Embeddings of graphs into higher-dimensional spaces==
| |||