Improving readability of static, straight-line graph drawings: A first look at edge crossing resolution through iterative vertex splitting

Information

• Publication Type: Journal Paper (without talk)
• Workgroup(s)/Project(s):
  • Visualization Group
• Date: November 2023
• DOI: 10.1016/j.cag.2023.09.010
• ISSN: 1873-7684
• Journal: COMPUTERS & GRAPHICS-UK
• Pages: 16
• Volume: 116
• Publisher: PERGAMON-ELSEVIER SCIENCE LTD
• Pages: 448 – 463
• Keywords: Edge crossings, Graph aesthetics, Network visualization, Vertex splitting

Abstract

We present a novel vertex-splitting approach to iteratively resolve edge crossings in order to improve the readability of graph drawings. Dense graphs, even when small in size (10 to 15 nodes in size) quickly become difficult to read with increasing numbers of edges, and form so-called “hairballs”. The readability of a graph drawing is measured using many different quantitative aesthetic metrics. One such metric of particular importance is the number of edge crossings. Classical approaches to improving readability, such as the minimization of the number of edge crossings, focus on providing overviews of the input graph by aggregating or sampling vertices and/or edges. However, this simplification of the graph drawing does not allow for detailed views into the data, as not all vertices or edges are rendered, and also requires sophisticated interaction approaches to perform well. To avoid this, our locally optimal vertex splitting approach aims to minimize the number of remaining edge crossings while also minimizing the number of vertices that need to be split. In each iteration, we identify the vertex contributing the largest number of edge crossings, remove it, locate the embedding locations of said vertex's two split copies, and determine each copy's unique adjacency. We conduct a user study with 52 participants to evaluate whether vertex splitting affects users’ abilities to conduct a set of graph analytical tasks on graphs 12 nodes in size. Users were tasked with identifying a vertex's adjacency, determining the shared neighbors of two vertices, and checking the validity of a set of paths. We ultimately conclude that within the context of small, dense graphs, systematic vertex splitting is preferred by participants and even positively impacts user performance, though at the cost of the time taken per task.

Additional Files and Images

Weblinks

• Entry in reposiTUm (TU Wien Publication Database)
• DOI: 10.1016/j.cag.2023.09.010

BibTeX

@article{ehlers-2023-iro,
  title =      "Improving readability of static, straight-line graph
               drawings: A first look at edge crossing resolution through
               iterative vertex splitting",
  author =     "Henry Ehlers and Anaïs Villedieu and Renata Raidou and
               Hsiang-Yun Wu",
  year =       "2023",
  abstract =   "We present a novel vertex-splitting approach to iteratively
               resolve edge crossings in order to improve the readability
               of graph drawings. Dense graphs, even when small in size (10
               to 15 nodes in size) quickly become difficult to read with
               increasing numbers of edges, and form so-called
               “hairballs”. The readability of a graph drawing is
               measured using many different quantitative aesthetic
               metrics. One such metric of particular importance is the
               number of edge crossings. Classical approaches to improving
               readability, such as the minimization of the number of edge
               crossings, focus on providing overviews of the input graph
               by aggregating or sampling vertices and/or edges. However,
               this simplification of the graph drawing does not allow for
               detailed views into the data, as not all vertices or edges
               are rendered, and also requires sophisticated interaction
               approaches to perform well. To avoid this, our locally
               optimal vertex splitting approach aims to minimize the
               number of remaining edge crossings while also minimizing the
               number of vertices that need to be split. In each iteration,
               we identify the vertex contributing the largest number of
               edge crossings, remove it, locate the embedding locations of
               said vertex's two split copies, and determine each copy's
               unique adjacency. We conduct a user study with 52
               participants to evaluate whether vertex splitting affects
               users’ abilities to conduct a set of graph analytical
               tasks on graphs 12 nodes in size. Users were tasked with
               identifying a vertex's adjacency, determining the shared
               neighbors of two vertices, and checking the validity of a
               set of paths. We ultimately conclude that within the context
               of small, dense graphs, systematic vertex splitting is
               preferred by participants and even positively impacts user
               performance, though at the cost of the time taken per task.",
  month =      nov,
  doi =        "10.1016/j.cag.2023.09.010",
  issn =       "1873-7684",
  journal =    "COMPUTERS & GRAPHICS-UK",
  pages =      "16",
  volume =     "116",
  publisher =  "PERGAMON-ELSEVIER SCIENCE LTD",
  pages =      "448--463",
  keywords =   "Edge crossings, Graph aesthetics, Network visualization,
               Vertex splitting",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2023/ehlers-2023-iro/",
}