A unit disk graph is defined by a collection of $n$ vertices corresponding to $n$ points on the plane, with an edge between any two vertices whose distance is at most $r$. Some $NP$-hard problems become solvable in polynomial time for unit disk graphs. I am interested in designing approximation algorithms by adapting such algorithms to general graphs as follows:

Let $A$ be an algorithm that solves an $NP$-hard problem in polynomial time in the special case of unit disk graphs.

  • Given a graph $G$, first embed it into the plane in such a way that vertex pairs connected by an edge tend to be close together, whereas vertex pairs that aren't connected tend to be farther apart.

Of course, the resulting graph is probably not going to be a unit disk graph, but hopefully it is close to such a graph in some sense.

  • Use the algorithm $A$ to find a solution for the graph.

Hopefully, if the embedding of $G$ is close to a unit disk graph, $A$ will return a good approximation to the $NP$-hard problem.

Has this type of thing been studied? In particular, I haven't been able to find an appropriate algorithm for the first item. "Low distortion Embeddings" is something related but different: There, the goal is that all edges should have similar lengths, whereas in my case I don't care about eliminating short edges. I just don't want any long edges.

I have an idea but it's rather silly: I thought of running a physical simulation in which we place an attractive force on edges between vertices that are far apart, and a repelling force on non-edges between vertices that are close together. We would wait for the system to reach an equilibrium, which hopefully would minimize some potential function that measures the distance between our embedding and a unit disk graph.

  • $\begingroup$ It seems that what you're calling a geometric graph here is also known as a unit disk graph. Not all graphs are unit disk graphs and recognizing whether a graph is a unit disk graph is NP-hard. In other words, an embedding where two points have an edge if and only if their distance is at most $r$ does not always exist. I'm not sure if that's what you mean concretely by "tends to be close", though, can you clarify this? $\endgroup$
    – Discrete lizard
    Commented Mar 7, 2021 at 12:48
  • $\begingroup$ Yes, thank you, that's exactly what I mean. I will update the question. $\endgroup$
    – Zur Luria
    Commented Mar 7, 2021 at 13:58
  • $\begingroup$ A concrete example of a graph that can't be represented as a unit disk graph is a star with more than 7 vertices (including the centre): All of the leaf disks need to overlap the central vertex's disk and not touch each other, but the kissing number of a circle is 6. $\endgroup$ Commented Mar 11, 2021 at 12:45


Your Answer

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

Browse other questions tagged or ask your own question.