Small grid embeddings of 3-polytopes

Details Small grid embeddings of 3-polytopes Small grid embeddings of 3-polytopes

2009-08-04

arxiv.org/abs/0908.0488v2

Computer Science

Computational Geometry

Scientific paper

We introduce an algorithm that embeds a given 3-connected planar graph as a convex 3-polytope with integer coordinates. The size of the coordinates is bounded by $O(2^{7.55n})=O(188^{n})$. If the graph contains a triangle we can bound the integer coordinates by $O(2^{4.82n})$. If the graph contains a quadrilateral we can bound the integer coordinates by $O(2^{5.46n})$. The crucial part of the algorithm is to find a convex plane embedding whose edges can be weighted such that the sum of the weighted edges, seen as vectors, cancel at every point. It is well known that this can be guaranteed for the interior vertices by applying a technique of Tutte. We show how to extend Tutte's ideas to construct a plane embedding where the weighted vector sums cancel also on the vertices of the boundary face.

Affiliated with

Also associated with

No associations

Rating

Small grid embeddings of 3-polytopes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Small grid embeddings of 3-polytopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Small grid embeddings of 3-polytopes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-557513