Schulz, André Drawing 3-polytopes with good vertex resolution. (English) Zbl 1217.05077 J. Graph Algorithms Appl. 15, No. 1, 33-52 (2011). 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. Cited in 5 Documents 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 \textit{A. Schulz}, J. Graph Algorithms Appl. 15, No. 1, 33--52 (2011; Zbl 1217.05077) Full Text: DOI EuDML