Obtaining Planarity by Contracting Few Edges

Details Obtaining Planarity by Contracting Few Edges Obtaining Planarity by Contracting Few Edges

2012-04-23

arxiv.org/abs/1204.5113v1

Computer Science

Data Structures and Algorithms

16 pages, 5 figures

Scientific paper

The Planar Contraction problem is to test whether a given graph can be made
planar by using at most k edge contractions. This problem is known to be
NP-complete. We show that it is fixed-parameter tractable when parameterized by
k.

Affiliated with

Also associated with

No associations

Rating

Obtaining Planarity by Contracting Few Edges 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 Obtaining Planarity by Contracting Few Edges, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Obtaining Planarity by Contracting Few Edges will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-444622