Drawing small planar graphs with Graphviz

user_2377652 0
Viewed 1084

I drew a small planar graph with Graphviz but in one place there's an intersection of two edges. I read on SO that not all planar graphs can be drawn without intersections because it's an NP-hard problem. I also read that there aren't even implemented complex algorithms in Graphviz that do that. But that intersection is as easy to fix as possible so there probably is a way to get rid of it.

Here are the options I used:

overlap = false;
splines = curved;
nodesep = 0.5;

And here's the graph: planar graph

So, is there a way of fixing that one intersection (25-38 with 7-18) without changing the order of edges like I did here? Isn't there like at least O(n^2) algorithm that would swap two vertices and check if the intersection disappeared?

planar-graph graphviz
1 Answers

This is kind of a hotfix:

Add an invisible edge between nodes 7 and 25, ie 7 -- 25 [style="invis"];. This clause may be added to the end of the graph definition so it shouldn't interfere with any automatic generation.

It feels like cheating, however, at least the order of the payload edges in the graph definition file remains untouched.

I cannot give an explanation of why this works,unfortunately. In particular, adding edges between other nodes incident to the offending edges does not produce the desired result.

Graphviz version: 2.38.0 (20140413.2041)

user_5889160
Related