Menu
I have an undirected graph with fixed node positions. The nodes cannot be moved, merged, removed or otherwise altered. The edges are fixed to their nodes, but do not have to be straight.
I need to know if it possible to 'bend' or 'draw' the edges such that the graph is planar (i.e. there are no edges crossing).
If such an algorithm or implementation exists, or you just have an idea on how to do it, please let me know!
842
Planar graph − A graph G is called a planar graph if it can be drawn in a plane without any edges crossed. If we draw graph in the plane without edge crossing, it is called embedding the graph in the plane. Non-planar graph − A graph is non-planar if it cannot be drawn in a plane without graph edges crossing.
A graph G is said to be planar if it can be represented on a plane in such a fashion that the vertices are all distinct points, the edges are simple curves, and no two edges meet one another except at their terminals.…
Definition. This undirected graph is defined as the complete bipartite graph . Explicitly, it is a graph on six vertices divided into two subsets of size three each, with edges joining every vertex in one subset to every vertex in the other subset. The graph is also known as the utility graph.
In a 3-connected planar graph, the sets of vertices and edges that border each face are the same in every planar drawing. There are planar graphs that are not 3-connected, like those in Figures 15.2 and 15.2, in which different planar drawings result in combinatorially different faces.
This question is answered by "J. Pach and R. Wenger. Embedding planar graphs at fixed vertex locations. Graphs Combin., 17:717–728, 2001" as:
Every planar graph on n vertices admits a planar embedding which maps each vertex to a prespecified distinct location and each edge to a polygonal curve with O(n) bends.
Such an embedding can be constructed in O(n^2) time.
So the answer is that you can construct such a graph if and only if the graph is planar. You can test if a graph is planar in O(n) time according to wikipedia.
172
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
