<p>In <a href="http://www.math.uu.nl/~Muell001/Papers/countingDGs.pdf">a paper with McDiarmid</a> we showed that the number of labelled graphs on $n$ 
vertices that are intersection graphs of disks is $n^{3n} \cdot \Theta(1)^n$
which is far less than $2^{{n\choose 2}}$, the total number of labelled graphs on $n$ vertices, and much more that $n^n \Theta(1)^n$, the number of planar graphs (touching graphs of disks) on $n$ vertices.  <br>
(Here I mean by $\Theta(1)^n$ a quantity that is bounded
below by $c^n$ and above by $C^n$ for some constants
$c,C &gt; 0$.) 
<br> <br></p>

<p>@ David : Thanks for mentioning my work!  <br>
I am also not aware of any paper that does the reduction to existential theory of the reals (ERT) for arbitrary disk graphs. 
However, in <a href="http://www.math.uu.nl/~Muell001/Papers/IntegerDiskSeg.pdf">another paper with McDiarmid</a>, we gave a construction 
for "embedding" line arrangements in a disk graph that could be
turned into a proof of completeness for ERT with some additional work along the 
lines of what we did in the paper with Kang.</p>

<p>Tobias Mueller</p>

CC BY-SA 3.0
2012-03-09T18:20:23.350Z
2012-03-10T11:38:57.380Z
2012-03-10T11:38:57.380Z
Tobias Mueller
<p>The definitive article is a <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.672">paper by Hlineny and Kratochvil</a> from 2001. In it they show that the problem of recognizing a disk intersection graph (your question) is NP-hard, which suggests that it will be difficult to come up with a clean characterization. They also point out that $K_{3,3}$ cannot be represented as the intersection of disks, answering the other part of your question. </p>

CC BY-SA 3.0
2012-03-08T00:19:10.447Z
More precisely it should be true that the problem is complete for the existential decision theory of the reals. This is known for unit disk intersection graphs — see http://homepages.cwi.nl/~mueller/Papers/SphericityDotproduct.pdf — but I don't know a reference for arbitrary disk intersection graphs.
David Eppstein
CC BY-SA 3.0
2012-03-08T01:59:11.240Z
Also, one can show using VC dimension arguments that the family of  any intersection graph defined by "simple" shapes is pretty limited and can not include many graphs. In particular, there is a constant size graph that they can not induce.
Sariel Har-Peled
CC BY-SA 3.0
2012-03-07T22:20:38.147Z
2012-03-07T22:20:38.147Z
Suresh Venkat
<p>We know that we can represent any planar graph by a set of circles in the plane, known as a <a href="http://en.wikipedia.org/wiki/Planar_graph#Coin_graphs">coin graph</a>. Each circle represents a vertex and there is an edge between two vertices if and only if the circles "kiss" at their boundary.</p>

<p>Suppose that instead we allow the circles to overlap, and represent an edge by a pair of circles that intersect in their interior? What class of graphs can we represent in this model? Clearly we can represent complete graphs (every circle intersects every other circle). Can we represent all graphs like this?</p>

<graph-theory><co.combinatorics><graph-algorithms><graph-drawing>
Representing non-planar graphs with overlapping circles
Joe
# Representing non-planar graphs with overlapping circles

(Asked by: username_0 on 2012-03-07)

We know that we can represent any planar graph by a set of circles in the plane, known as a [coin graph](http://en.wikipedia.org/wiki/Planar_graph#Coin_graphs). Each circle represents a vertex and there is an edge between two vertices if and only if the circles "kiss" at their boundary.

Suppose that instead we allow the circles to overlap, and represent an edge by a pair of circles that intersect in their interior? What class of graphs can we represent in this model? Clearly we can represent complete graphs (every circle intersects every other circle). Can we represent all graphs like this?

**Tags:** graph-theory, co.combinatorics, graph-algorithms, graph-drawing

---

## 2 answers

### Answer by username_2 on 2012-03-07. Score: 20 | Accepted answer

The definitive article is a [paper by Hlineny and Kratochvil](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.672) from 2001. In it they show that the problem of recognizing a disk intersection graph (your question) is NP-hard, which suggests that it will be difficult to come up with a clean characterization. They also point out that $K\_{3,3}$ cannot be represented as the intersection of disks, answering the other part of your question.

> **Comments:**
> **username_3**: More precisely it should be true that the problem is complete for the existential decision theory of the reals. This is known for unit disk intersection graphs — see http://homepages.cwi.nl/~mueller/Papers/SphericityDotproduct.pdf — but I don't know a reference for arbitrary disk intersection graphs.  
> **username_4**: Also, one can show using VC dimension arguments that the family of  any intersection graph defined by "simple" shapes is pretty limited and can not include many graphs. In particular, there is a constant size graph that they can not induce.  

---

### Answer by username_1 on 2012-03-09. Score: 9

In [a paper with McDiarmid](http://www.math.uu.nl/~Muell001/Papers/countingDGs.pdf) we showed that the number of labelled graphs on $n$
vertices that are intersection graphs of disks is $n^{3n} \cdot \Theta(1)^n$
which is far less than $2^{{n\choose 2}}$, the total number of labelled graphs on $n$ vertices, and much more that $n^n \Theta(1)^n$, the number of planar graphs (touching graphs of disks) on $n$ vertices.   
(Here I mean by $\Theta(1)^n$ a quantity that is bounded
below by $c^n$ and above by $C^n$ for some constants
$c,C > 0$.)

@ David : Thanks for mentioning my work!   
I am also not aware of any paper that does the reduction to existential theory of the reals (ERT) for arbitrary disk graphs.
However, in [another paper with McDiarmid](http://www.math.uu.nl/~Muell001/Papers/IntegerDiskSeg.pdf), we gave a construction
for "embedding" line arrangements in a disk graph that could be
turned into a proof of completeness for ERT with some additional work along the
lines of what we did in the paper with Kang.

Tobias Mueller


---

