Autor:	Furst, Merrick L., Gross, Jonathan L., McGeoch, Lyle A.
Rok vydání:	1987
Předmět:	Mathematics::Complex Variables Mathematics::Geometric Topology Computer science
DOI:	10.7916/d8n87js8
Popis:	The computational complexity of constructing the imbeddings of a given graph into surfaces of different genus is not well-understood. In this paper, topological methods and a reduction to linear matroid parity are used to develop a polynomial-time algorithm to find a maximum-genus cellular imbedding. This seems to be the first imbedding algorithm for which the running time is not exponential in the genus of the imbedding surface.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::e2d619b01fa763cbdb15d902108e31fd Zobrazit plný text záznamu