<p>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.</p>

CC BY-SA 3.0
2016-06-07T08:31:59.090Z
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.
Andrew Morgan
CC BY-SA 3.0
2016-06-07T09:20:21.997Z
@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 ?
KKS
CC BY-SA 3.0
2016-06-07T10:16:34.893Z
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.
Andrew Morgan
CC BY-SA 3.0
2016-06-07T10:53:52.440Z
@Andrew Morgan I thought $r$ representation length should be bounded by some polynomial of the input length, isn't it ?
KKS
CC BY-SA 3.0
2016-06-07T17:23:28.450Z
I think I might see one issue I've swept under the rug that you might be referring to: if the planar embedding has very long edges (say the nearest integer is like $2^n$), then super-polynomially many circles would likely be needed to represent that edge. That said, [this link](https://www.ics.uci.edu/~eppstein/gina/schnyder/) suggests that isn't really an issue if we pick the right planar embedding.
Andrew Morgan
CC BY-SA 3.0
2016-06-07T17:23:34.137Z
But other than that, setting "a bunch" to one plus the number of vertices works, and geometrically it's clear that the radii of the disks can be chosen to be inverse polynomial. This gives the overall reduction only a polynomial blowup.
Andrew Morgan
CC BY-SA 3.0
2016-06-07T17:44:24.747Z
See https://en.wikipedia.org/wiki/Circle_packing_theorem — disk packing graphs and planar graphs are the same thing. No subdivision of edges into paths required.
David Eppstein
<computational-geometry><complexity>
Complexity of Maximum Independent Set (or Vertex Cover) on disk packing graphs
KKS
# Complexity of Maximum Independent Set (or Vertex Cover) on disk packing graphs

(Asked by: username_0 on 2016-06-07)

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.

**Tags:** computational-geometry, complexity
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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 ?  
> **username_1**: 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.  
> **username_0**: @Andrew Morgan I thought $r$ representation length should be bounded by some polynomial of the input length, isn't it ?  
> **username_1**: I think I might see one issue I've swept under the rug that you might be referring to: if the planar embedding has very long edges (say the nearest integer is like $2^n$), then super-polynomially many circles would likely be needed to represent that edge. That said, [this link](https://www.ics.uci.edu/~eppstein/gina/schnyder/) suggests that isn't really an issue if we pick the right planar embedding.  
> **username_1**: But other than that, setting "a bunch" to one plus the number of vertices works, and geometrically it's clear that the radii of the disks can be chosen to be inverse polynomial. This gives the overall reduction only a polynomial blowup.  
> **username_2**: See https://en.wikipedia.org/wiki/Circle_packing_theorem — disk packing graphs and planar graphs are the same thing. No subdivision of edges into paths required.  

---

## 0 answers

