Moving Vertices to Make Drawings Plane

Details Moving Vertices to Make Drawings Plane Moving Vertices to Make Drawings Plane

2007-06-07

arxiv.org/abs/0706.1002v3

Computer Science

Computational Geometry

This paper has been merged with http://arxiv.org/abs/0709.0170

Scientific paper

A straight-line drawing $\delta$ of a planar graph $G$ need not be plane, but can be made so by moving some of the vertices. Let shift$(G,\delta)$ denote the minimum number of vertices that need to be moved to turn $\delta$ into a plane drawing of $G$. We show that shift$(G,\delta)$ is NP-hard to compute and to approximate, and we give explicit bounds on shift$(G,\delta)$ when $G$ is a tree or a general planar graph. Our hardness results extend to 1BendPointSetEmbeddability, a well-known graph-drawing problem.

Affiliated with

Also associated with

No associations

Rating

Moving Vertices to Make Drawings Plane 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 Moving Vertices to Make Drawings Plane, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Moving Vertices to Make Drawings Plane will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-442219