Inapproximability of Orthogonal Compaction

Details Inapproximability of Orthogonal Compaction Inapproximability of Orthogonal Compaction

2011-08-23

arxiv.org/abs/1108.4705v3

Computer Science

Computational Geometry

Updated to the final version to appear in the Journal of Graph Algorithms and Applications

Scientific paper

We show that several problems of compacting orthogonal graph drawings to use the minimum number of rows, area, length of longest edge or total edge length cannot be approximated better than within a polynomial factor of optimal in polynomial time unless P = NP. We also provide a fixed-parameter-tractable algorithm for testing whether a drawing can be compacted to a small number of rows.

Affiliated with

Also associated with

No associations

Rating

Inapproximability of Orthogonal Compaction 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 Inapproximability of Orthogonal Compaction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inapproximability of Orthogonal Compaction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-376929