Questions tagged [planar-graphs]
The planar-graphs tag has no usage guidance.
4
questions
3
votes
0answers
148 views
Convert DAG whose transitive reduction is non-planar to a planar DAG with same transitive closure
For any non-planar DAG, we can compute the transitive reduction, and sometimes it will be planar (e.g. $K_5$).
However, sometimes the transitive reduction is also non-planar. For example, $K_{3, 3}$'...
3
votes
1answer
617 views
Creating a 2D map of objects given a sparse matrix of pairwise distances
I have a set of points on the two-dimensional plane, but their locations are not given to me. I am given the distance between some pairs of the points. However, I only know these differences for ...
3
votes
2answers
82 views
Finding closest edge to a point in a planar graph
I have a point location problem (in a planar graph) with a twist: rather then finding which region the point is located in, I would like to find the closest segment (edge) to a point, ideally with a <...
2
votes
1answer
225 views
Edge removal to convert a non-planar DAG to a planar DAG while maintaining reachability?
Is there an algorithm that removes edges to convert a non-planar DAG to a planar DAG while maintaining reachability? For example, the graph $G$ below is non-planar:
but, by removing certain edges to ...
