Project Details
Description
In 1996 Thomassen proved the conjecture made by R.B.Richter
in 1991, that the graph genus problem for cubic
graphs is NP-complete. Furthermore, we have obtained
a relatively short proof of the deep result in the
Robertson-Seymour theory that, for any fixed surface,
there are only finitely many obstructions for
the graph embedding problem in that surface.
Since 1997, the work in this project has concentrated on the monograph on graphs on surfaces written in colloboration with Bojan Mohar, University of Ljubljana. This work is planned to be completed in 2000
in 1991, that the graph genus problem for cubic
graphs is NP-complete. Furthermore, we have obtained
a relatively short proof of the deep result in the
Robertson-Seymour theory that, for any fixed surface,
there are only finitely many obstructions for
the graph embedding problem in that surface.
Since 1997, the work in this project has concentrated on the monograph on graphs on surfaces written in colloboration with Bojan Mohar, University of Ljubljana. This work is planned to be completed in 2000
| Status | Active |
|---|---|
| Effective start/end date | 01/01/1996 → … |
Collaborative partners
- Technical University of Denmark (lead)
- Unknown (Project partner)
Fingerprint
Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.