Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids

2011/02/13 by Francisco Santos, Santos, Francisco · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #cs.CG #math.CO

paper · pdf · doi:10.48550/arxiv.1102.2645

This paper and arXiv:1101.3050 have been merged, forming now the paper arXiv:1104.2630

openalex publication_date 2011/02/13 · arxiv created 2011/04/15 · arxiv updated 2011/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A prismatoid is a polytope with all its vertices contained in two parallel facets, called its bases. Its width is the number of steps needed to go from one base to the other in the dual graph. The author recently showed in arXiv:1006.2814 that the existence of counter-examples to the Hirsch conjecture is equivalent to that of d-prismatoids of width larger than d, and constructed such prismatoids in dimension five. Here we show that the same is impossible in dimension four. This is proved by looking at the pair of graph embeddings on a 2-sphere that arise from the normal fans of the two bases of Q.

Citations

• A counterexample to the Hirsch conjecture
• An Euler characteristic proof that 4-prismatoids have width at most 4

Cited by

• An Euler characteristic proof that 4-prismatoids have width at most 4
• Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids

Related

• An Euler characteristic proof that 4-prismatoids have width at most 4
• Drums of high width
• Bounds on the diameters of r-stacked and k-neighborly polytopes
• Embeddings of four-valent framed graphs into two-surfaces
• Twin-width of graphs on surfaces