Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way - Dickerson, Matthew; Eppstein, David; Goodrich, Michael; Meng, Jeremy (Journal of Graph Algorithms and Applications, 2005)
We introduce a new approach for drawing diagrams.Our approach is to use a technique we call confluent drawingfor visualizing non-planar graphs in a planar way. This approachallows us to draw, in a crossing-free manner, graphs-such assoftware interaction diagrams-that would normally have manycrossings. The main idea of this approach is quite simple: we allowgroups of edges to be merged together and drawn as "tracks"(similar to train tracks). Producing such confluent drawingsautomatically from a graph with many crossings is quite challenging,however, we offer a heuristic algorithm(one version for undirected graphs and one version for directed ones)to test if anon-planar graph can be drawn efficiently in a confluent way. Inaddition, we identify several large classes of graphs that can becompletely categorized as being either confluently drawable orconfluently non-drawable. <!---->