Are Crossings Important for Drawing Large Graphs?

Kobourov, Stephen G. and Pupyrev, Sergey and Saket, Bahador (2014) Are Crossings Important for Drawing Large Graphs? In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 234-245(Official URL:

Full text not available from this repository.


Reducing the number of edge crossings is considered one of the most important graph drawing aesthetics. While real-world graphs tend to be large and dense, most of the earlier work on evaluating the impact of edge crossings utilizes relatively small graphs that are manually generated and manipulated. We study the effect on task performance of increased edge crossings in automatically generated layouts for graphs, from different datasets, with different sizes, and with different densities. The results indicate that increasing the number of crossings negatively impacts accuracy and performance time and that impact is significant for small graphs but not significant for large graphs. We also quantitatively evaluate the impact of edge crossings on crossing angles and stress in automatically constructed graph layouts. We find a moderate correlation between minimizing stress and the minimizing the number of crossings.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_20
Classifications: D Aesthetics > D.999 Others
G Algorithms and Complexity > G.420 Crossings
M Methods > M.400 Force-directed / Energy-based
P Styles > P.720 Straight-line

Actions (login required)

View Item View Item