Questions tagged [planar-graphs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...