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

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
  • 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.

  • Lin, 1992, PhD thesis: Analysis of algorithms for drawing graphs
  • Eades & Lin, 2000: Spring algorithms and symmetry (doi)
  • Chuang & Yen, 2002: On nearly symmetric drawings of graphs (doi)
  • Lin & Yen, 2012: A new force-directed graph drawing method based on edge–edge repulsion (doi, pdf)

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)