The graph genus problem is NP-complete

1989/12/01 by Carsten Thomassen · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Biology #Combinatorics #Genus #Graph #Mathematics #Zoology

paper · doi:10.1016/0196-6774(89)90006-0

crossref issued 1989/12/01 · crossref published 1989/12/01 · crossref published-print 1989/12/01 · openalex publication_date 1989/12/01 · crossref created 2005/02/10 · crossref deposited 2019/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/09 · crossref indexed 2026/07/21

Cited by

• On the page number of RNA secondary structures with pseudoknots
• A separator theorem for graphs with an excluded minor and its applications
• Homeomorphism of 2-Complexes is Graph Isomorphism Complete
• Genus (mathematics) [wikipedia]