17
$\begingroup$

We know that we can represent any planar graph by a set of circles in the plane, known as a coin graph. 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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
20
$\begingroup$

The definitive article is a paper by Hlineny and Kratochvil 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.

Improve this answer
$\endgroup$
2
  • 7
    $\begingroup$ 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 homepages.cwi.nl/~mueller/Papers/SphericityDotproduct.pdf — but I don't know a reference for arbitrary disk intersection graphs. $\endgroup$
    – David Eppstein
    Mar 8, 2012 at 0:19
  • 7
    $\begingroup$ 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. $\endgroup$
    – Sariel Har-Peled
    Mar 8, 2012 at 1:59
9
$\begingroup$

In a paper with McDiarmid 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, 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

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.