Planar graph emulators: Fellows' conjecture
Martin Derka · 2010
This paper deals with the problem which graphs have finite planar emulators and the related Fellows' conjecture (stated in 1985). It was open for more than 20 years until the end of 2008, when it was surprisingly disproved. It turned out that we actually do not know much about the class of non-projective graphs with finite planar emulators and this field became open for new research. In the paper we study the properties of this class -- we show that if the graph is non-projective and has a finite planar emulator, then it must be a planar expansion of an internally 4-connected graph from a specific finite set, or contain one of six minor minimal non-projective graphs. We list this set of 176 graphs and finally suggest a new conjecture replacing Fellows' one.