×

Drawing 3-polytopes with good vertex resolution. (English) Zbl 1217.05077

Summary: We study the problem how to obtain a small drawing of a 3-polytope with Euclidean distance between any two points at least 1. The problem can be reduced to a one-dimensional problem, since it is sufficient to guarantee distinct integer \(x\)-coordinates. We develop an algorithm that yields an embedding with the desired property such that the polytope is contained inside a \(2(n - 2) \times 2 \times 1\) box. The constructed embedding can be scaled to a grid embedding whose \(x\)-coordinates are contained in \([0, 2(n - 2)]\). Furthermore, the point set of the embedding has a small spread, which differs from the best possible spread only by a multiplicative constant.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C62 Graph representations (geometric and intersection representations, etc.)
05C12 Distance in graphs
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI EuDML