Graphs on Surfaces

    Project Details


    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
    Effective start/end date01/01/1996 → …