3

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?

user1
  • 945
  • 2
  • 13
  • 37
  • 3
    There are `O(N)` algorithms [[1](https://archive.org/details/PlanarityTestingByPathAddition) [2](https://dl.acm.org/citation.cfm?id=321852)] to test for planarity and they do it by creating a planar embedding. It is always possible to create an embedding of a planar graph without edge-crossings (since that is the definition of a planar graph) and it is not an NP-hard problem and if there are answers stating that then they are wrong. That said, I have never used GraphVis so can't help you with solving it in that program. – MT0 Oct 03 '17 at 20:26
  • @MT0 I know that there are fast planar graph checks. I meant that drawing planar graphs is NPH. But I was incorrect. I checked and I actually [read](https://stackoverflow.com/a/2348551/2377652) that drawing a graph with least edges crossing is NPH. My bad. – user1 Oct 11 '17 at 18:14
  • Drawing a non-planar graph with minimal edge crossings is hard - drawing a planar graph with no edge crossings is a problem that has been solved in linear time (`O(N)`) - see the first link in my previous comment for one method amongst many. – MT0 Oct 11 '17 at 18:59

1 Answers1

3

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)

collapsar
  • 17,010
  • 4
  • 35
  • 61