Non-revisiting paths on surfaces with low genus

✍ Scribed by H. Pulapaka; A. Vince

• Book ID: 104113948
• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 601 KB
• Volume: 182
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(97)00151-9

✦ Synopsis

The non-revisiting path conjecture for polytopes, which is equivalent to the Hirsch conjecture, is open. However, for polyhedral maps on surfaces, we have recently proved the conjecture false for all orientable surfaces of genus g/> 2 and all nonorientable surfaces of nonorientable genus h/>4. In this paper, a unified, elementary proof of the non-revisiting path conjecture is given for the sphere, projective plane, toms and Klein bottle. Only the case of the connected sum of three copies of the projective plane remains open. In connection with the notion of the representativity p of a surface embedding, it is shown that the non-revisiting path property holds for all surfaces of representativity p>~4, but there is a polyhedral map with representativity 3 for which the non-revisiting path property fails.