Graph drawing
Graph drawing is an important practical aspect of any human-centric use of graphs. The seemingly simple task of drawing a graph quickly leads to serious mathematical and algorithmic problems.
Software
Although there is lots of graph visualization software, very little of it does any layout beyond the usual “physics-based” layouts. Sofware packages that do serious graph layout include:
- Graphviz (GitLab )
- Thirty years on, still the gold standard for layered graph drawing
- Available in browser as Viz.js
- Dagre (GitHub )
- Open Graph Drawing Framework (GitHub )
- Chimani et al, 2013: The Open Graph Drawing Framework (OGDF) (pdf)
- Ch. 17 in Tamassia, ed., 2013
- C++ library developed by graph drawing experts, offering many algorithms
- Name notwithstanding, it seems to be not very open: the license is GPL and development happens in a non-public repository
- Chimani et al, 2013: The Open Graph Drawing Framework (OGDF) (pdf)
General literature
Books and surveys
- Di Battista, Eades, Tamassia, Tollis, 1999: Graph drawing: Algorithms for the
visualization of graphs
- The standard reference on graph drawing
- Ch. 2 has useful overview of drawing methods and intermediate representations (Fig. 2.12)
- Kaufmann & Wagner, eds., 2001: Drawing graphs: Methods and models (doi)
- Tamassia, ed., 2013: Handbook of graph drawing and visualization (online )
- Mchedlidze, 2018, lecture notes: Algorithms for graph visualization (slides)
Displaying symmetries
In symmetric graph drawing, the symmetries of the graph (graph automorphisms) are supposed to manifest as symmetries of the drawing (restrictions of plane isometries). This is not always possible, nor is it algorithmically easy.
Surveys
- Eades & Hong, 2013: Symmetric graph drawing (pdf)
- Ch. 3 in Tamassia, ed., 2013
Papers
Much work on symmetric graph drawing has been done by Seok-Hee Hong et al:
- Hong & Eades, 2001-2006: Drawing planar graphs symmetrically
- I: Triconnected planar graphs (with McKay) (doi , tech report )
- II: Biconnected planar graphs (doi, tech report )
- III: Oneconnected planar graphs (doi, tech report )
- IV: Disconnected planar graphs (doi, tech report )
- Abelson, Hong, Taylor, 2007: Geometric automorphism groups of graphs (doi)
- Extended abstract in: Abelson, Hong, Taylor, 2002: A group-theoretic method for drawing graphs symmetrically (doi)
- Hong & Nagamochi, 2010: A linear-time algorithm for symmetric convex drawings of internally triconnected plane graphs (doi)
Force-directed graph drawings sometimes display symmetries. A partial theoretical explanation has been given for this phenomenon by Eades & Lin.
Crossing minimization
Minimizing edge crossings is one of the most important aesthetic critera in graph drawing, layered or otherwise. It is NP-hard in every formulation and generally hard to solve in practice. Theoretically speaking, the crossing number (curved or rectilinear) remains poorly understood.
- Jünger & Mutzel, 1997: 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms (doi, eudml , pdf)
- Bastert & Matuszewski, 2001: Layered drawing of digraphs, Sec. 5.4: Crossing reduction
- Buchheim et al, 2013: Crossings and planarization (pdf)
- Ch. 2 in Tamassia, ed., 2013
- Exact and heuristic methods for crossing minimization in undirected graphs
Confluent graph drawing
In confluent drawing, edges are bundled to reduce crossing and minimize clutter.
- Dickerson, Eppstein, Goodrich, Meng, 2005: Confluent drawings: Visualizing non-planar diagrams in a planar way (doi, pdf)
- Eppstein, Goodrich, Meng, 2007: Confluent layered drawings (doi, arxiv)
- Bach et al, 2016: Towards unambigous edge bundling: Investigating confluent drawings for network visualization (pdf, website )
Literature on specific methods
Layered drawing
Layered drawing of directed graphs is also known as hierarchical, rank-based, or Sugiyama-style graph drawing.
Surveys
- Di Battista et al, 1999, Sec. 2.4: The hierarchical approach & Ch. 9: Layered drawings of digraphs
- Bastert & Matuszewski, 2001: Layered drawings of digraphs (doi)
- Ch. 5 in Kaufmann & Wagner, eds., 2001
- Healy & Nikolov, 2013: Hierarchical drawing algorithms (pdf)
- Ch. 13 in Tamassia, ed., 2013
Original papers
- Sugiyama, Tagawa, Toda, 1981: Methods for visual understanding of hierarchical system structures (doi)
- Gansner, Koutsofios, North, Vo, 1993: A technique for drawing directed graphs
(doi)
- Extension of the Sugiyama method
- Main reference for Graphviz dot algorithm
Force-directed drawing
Force-directed drawings of graphs, often undirected, are loosely inspired by Newtonian physics. The algorithms are popular because they are easy to implement while often producing decent results.
Surveys
- Di Battista et al, 1999, Ch. 10: Force-directed methods
- Brandes, 2001: Drawing on physical analogies (doi)
- Kobourov, 2013: Force-directed drawing algorithms (pdf)
- Ch. 3 in Tamassia, ed., 2013
Papers
- Chen & Buja, 2013: Stress functions for nonlinear dimension reduction,
proximity analysis, and graph drawing (pdf)
- Nice paper explaining connection between multidimensional scaling and force-directed graph drawing
- Uses a four-parameter family of stress/energy functions derived from the Box-Cox transform
Dominance drawing
Dominance drawing is a family of methods for drawing directed graphs on a grid. It works best for transitively reduced planar DAGs but has extensions to other settings.
- Di Battista et al, 1999, Ch. 4: Planar orientations, Sec. 4.7: Dominance
drawings
- Alternate manuscript with similar content (pdf)
- Di Battista, Tamassia, Tollis, 1992: Area requirement and symmetry display of planar upward drawings (doi)
- Kornaropoulos & Tollis, 2012: Weak dominance drawings for directed acyclic graphs (doi)
- Ortali & Tollis, 2019: Multidimensional dominance drawings (arxiv)