×

Confluent layered drawings. (English) Zbl 1118.68103

Summary: We combine the idea of confluent drawings with Sugiyama-style drawings in order to reduce the edge crossings in the resultant drawings. Furthermore, it is easier to understand the structures of graphs from the mixed-style drawings. The basic idea is to cover a layered graph by complete bipartite subgraphs (bicliques), then replace bicliques with tree-like structures. The biclique cover problem is reduced to a special edge-coloring problem and solved by heuristic coloring algorithms. Our method can be extended to obtain multi-depth confluent layered drawings.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C62 Graph representations (geometric and intersection representations, etc.)