Minimize intersecting lines in a web graph

Question

I implement (considering this in fact) a control that allows users to create a web diagram from a number of nodes. The goal will be to create a “flow chart” of sorting from a series of questions asked by another piece of software; for each question, the selected answer determines which question should be asked next. It's a bit FSMish, but much smarter than linearly promoting questions of the form "If you answered X to question Y, answer the following ...". A graph is a network and is not guaranteed to be a tree, because the user who defines the graph may want to ask a couple of subsequent questions and then return to the “normal” interrogation line, so two different nodes can merge with the same child node. However, the network is guaranteed not to be circular and has one starting point, so there is a finite number of paths through the graph and the entire final length.

That is the question. I would like to have a “organize” button (or just automatically organize) that rebuilds the nodes so that the number of lines connecting the network nodes that should cross each other is minimized. Most charting tools have the ability to do this, but my Google-fu could not find a universal algorithm of this type. I defined it as the “intersection number” problem, but there seems to be no general solution to find the minimum number of intersections of a graph with V nodes and paths E and that any such solution will be NP-hard (if a particular subtask can be solved in one operation, then the complete problem can be solved in polynomial time). In addition, none of the links that I found contains detailed algorithms that can lay out a graph with a minimal (not to mention minimal) intersecting number.

Any clues?

EDIT: I gave Sharkos a tick for his excellent recommendations. However, assuming the graph has a specific starting point, is unidirectional and non-circular, the working algorithm (possibly not optimal) is actually quite simple. In pseudo code:

" Give all nodes an initial XScore, YScore and LinkScore of 0 Determine the start node (either designated, or the one not linked to by any other) Set start node XScore and YScore to 1 Set running YScore = 1 Start recursion for each path from node if node on other end has XScore <= current set other node XScore to current + 1 if node on other end has YScore <= running YScore set other node YScore to running YScore increment other node LinkScore Recurse with node on other end Increment running YScore Order nodes by XScore, then YScore. --If the graph happens to be planar, we're done. --To minimize crossover: for each XScore for each node with that XScore if the next node with the same XScore has a higher LinkScore swap the two nodes, exchanging YScores 

Answer 1

Here is a master's thesis on a topic that gives some algorithms with discussion and provides links to lots and many different people, from exact algorithms to approximation algorithms.

However, for a rather simple, specific pseudo-code version of the “method of planes”, apparently (not an expert, although I studied graph theory and this sounds plausibly useful), the general approximation is, see section 2.5 in this chapter from the Handbook on Graphic Drawing and Visualization which is freely available on the Internet.

Hope you like it?