I'm interested in complexity results for Maximum Independent Set (or Vertex Cover) problem over the class of disk packing graphs. Having a set of disks we build a graph that has its vertices at the disk centers whereas its edge connects two vertices that correspond touching disks.

  • $\begingroup$ For the exact problems, VC/MIS over disk graphs are equivalent to the same problem over planar graphs. Disk -> planar is obvious. For the other direction, replace each edge in the planar graph by a bunch of parallel "lines", where each line is a chain of an even number of small disks. "A bunch" is such that any optimal solution is an optimal solution to the original problem plus picking an appropriate half of the vertices along each newly-added line. $\endgroup$ – Andrew Morgan Jun 7 '16 at 8:31
  • $\begingroup$ @Andrew Morgan There is some weak point in this argument which is in choosing radii of disks to be added. Number of added disks should be proportional to the number of edges and must be independent of particular planar graph drawing. Do you agree ? $\endgroup$ – KKS Jun 7 '16 at 9:20
  • $\begingroup$ I don't see why the number of added disks should be proportional to the number of edges, or be independent of the planar graph drawing. I was just establishing a polynomial-time equivalence between the exact decision versions of the problems; such a reduction doesn't have to do things like preserve the exact size of the solution or the graph structure. $\endgroup$ – Andrew Morgan Jun 7 '16 at 10:16
  • $\begingroup$ @Andrew Morgan I thought $r$ representation length should be bounded by some polynomial of the input length, isn't it ? $\endgroup$ – KKS Jun 7 '16 at 10:53
  • 1
    $\begingroup$ See en.wikipedia.org/wiki/Circle_packing_theorem — disk packing graphs and planar graphs are the same thing. No subdivision of edges into paths required. $\endgroup$ – David Eppstein Jun 7 '16 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.