What is graph layout?
A graph is a set of nodes and edges that connect the nodes to each other. Nodes can represent any object, task, or state while the edges represent the relationships and dependencies between them.
You can imagine that a graph containing any more than a few dozen nodes and edges can quickly become complex to draw clearly, and even more difficult to decipher any meaning from it. This is where graph layout comes in.
Graph layout is the science and art of positioning nodes, connectors, labels, subgraphs, and the routing of edges between them so that the resulting drawings are unambiguous and easy to interpret.
Graph layout has the following optimization criteria:
- keep connected nodes close to each other,
- position objects overlap-free,
- and reduce the number of edge crossings.
Good graph layout allows humans to easily see each element, follow each edge, and extrapolate information that may have been hidden in the data.
An example orthogonal graph layout.
An example symmetric graph layout.
Graph layout reveals the trends and patterns hidden in data.
Who needs graph layout?
Graph layout has application across the private and public sectors, and is used by developers, researchers, IT administrators, scientists, data scientists, and more. Graph layout software helps them analyze complex information and answer important questions.
When applied effectively, graph layout can help you visualize and understand:
- Dependencies
- Networks
- Architectures and models
- Flows and impacts
A simple scenario
The following scenario highlights the benefits of graphs and good graph layout.
Looking at the lists of names below, it would take some minutes to answer questions such as:
- Who is at the top of the reporting chain?
- How many people report to Frank?
Looking at bad graph layout makes answering those questions even more challenging. But with a good graph layout, the answers are immediately apparent.
Answering your questions is easier with graphs and good graph layout.
A graph of the power subsystem in an electric hybrid vehicle using the orthogonal graph layout technique.
A zoomed-in view of a graph that showcases good edge routing and node and label layout.
Layout techniques and challenges
Graph layout is a complex field of study that has been around for decades. Considerable research on graph layout has been conducted in the United States, Germany, Italy, Latvia, Greece, and Australia with many people receiving Ph.D. degrees in graph layout.
Graph layout problems are more difficult than they may first appear, and in fact many of these problems are in the computationally most difficult category of problems. Therefore, it is necessary to have highly specialized graph layout techniques in order to reliably create high-quality graph visualizations for complex, large graphs.
Researchers in this field have developed a number of graph layout styles and algorithms that are well-known, including spring-embedder, hierarchical, orthogonal, and circular layout styles. Open-source and commercial graph layout toolkits using these layout techniques abound. But there are considerable hurdles going from academic research to quality commercial or open-source graph layout systems. Not all techniques and tools are created equally, and many attempts at commercialization have failed.
As with many things, the devil is in the details when you consider the optimization goals mentioned previously, and factor in the number of nodes and edges and any special requirements for the graph. Good graph layout quickly becomes difficult to achieve, and even more challenging to make performant.
Good graph layout should align with user expectations, and provide insight and value not otherwise apparent in the data. It shouldn't be a distraction. And users shouldn't have to wait long to see results.
This is where many tools fail. They distract with messy layouts or worse, hairball-like graphs.
Graphics Specialized for Your Graph Data Application
Perspectives is optimized with high-speed graphics capabilities and HTML5 canvas graphics to create the best in class graph visualizations for your application. You can use Perspectives HTML classes embed the visualization components into your web application and when the HTML class is assigned to any HTML tag, such as <span> or <div>, the tag will be interpreted as a component, regardless of its type.
Tom Sawyer Perspectives provides unrivaled graph layout and visualization
Tom Sawyer Software has a decades-long track record of innovation when it comes to automatic graph layout and supporting graph use cases. Our CEO, Brendan Madden, has worked on graph layout since 1985, when he started his career at IBM and built an automatic layout system at IBM Research and another at IBM Santa Teresa Laboratories. Today, our products are the direct result of this long history and experience with graphs.
Tom Sawyer Perspectives is a low-code application development platform that enables software developers to build custom graph visualization and analysis applications to meet their unique graph use cases and includes the graph layout capabilities we spent decades perfecting.
No other commercial or open-source toolkit compares to our graph layout capabilities, which include:
- automated global and incremental layout of nodes, edges, labels, and connectors
- powerful and flexible edge routing technology
- support for cycles, reflexive edges, and multi-edges
- support for complex nested graph layout
- support for connected components and disconnected nodes
- support of rich graph features including labels and connectors
- a multitude of layout constraints and drawing customization features including swimlanes and control of node positions
A graph with node and edge labels.
A graph with connectors.
Tom Sawyer Perspectives places the power of layout algorithms into your users' hands
Tom Sawyer Perspectives sophisticated graph layout is put into the hands of the users who need it. Our automated graph layout:
- provides time-saving automated results
- enables users to focus on the important analysis tasks at hand
- provides users with the insight they need
An example application built with Tom Sawyer Perspectives that showcases integrated graph and data visualization.
Bundle Layout
This proprietary and patented graph layout style merges, or bundles, the common edges between nodes into one when possible. Instead of seeing five edges leading from five nodes to a common destination, some of those edges bundle together, eliminating the hairball effect often seen in large graphs and making the overall graph easier to read. Our bundle layout produces overlap-free drawings and can process several thousand nodes per second.
Bundle layout is best suited to large and dense graphs with many thousands of nodes and edges, but can be equally effective and beautiful in smaller data sets.
Circular Layout
This patented graph layout style clusters the nodes into groups, and places the nodes in each cluster on a circle, carefully ordering them so as to reduce crossings and place adjacent nodes close to each other. Additionally, some nodes may be placed inside a cluster if they connect only to other nodes in the same cluster.
Circular layout is best suited to graphs that show groups or clusters. It excels at visualizing networks, such as network topologies, gene interaction diagrams, and social networks.
Hierarchical Layout
This graph layout style arranges nodes into layers, either horizontal or vertical, in such a way that most edges go downwards or from left to right from one layer to the next, and then nodes within each layer are rearranged to minimize crossings. Our hierarchical layout also minimizes the overall number of bends in the graph and provides an orthogonal edge routing option, which produces overlap-free drawings.
Hierarchical layout is best suited to use cases where edge direction matters, such as an organizational chart, a flow graph, or a graph of dependencies.
Orthogonal Layout
Orthogonal Layout allows edges to run horizontally and vertically. It uses a multiphase approach that coordinates node placement, edge routing, and labeling while accounting for rules and constraints in the graph. Our implementation produces overlap-free drawings.
It is particularly suited to systems models, entity relationship diagrams, and circuit and chip design, while its clean drawings also work well for many other use cases.
Symmetric Layout
This graph layout style applies attractive and repulsive forces between nodes to produce a layout with short edge lengths and well-separated nodes. Tom Sawyer Software has refined this well-known technique to reduce the hairball-like effect that can occur in larger graphs. Many open-source and commercial tools implement more basic versions of this algorithm, often with less effective results. Our symmetric layout produces non-overlapping drawings, supports constraints, and includes specialized processing that can lay out several thousand nodes per second.
Symmetric layout is especially useful when the structure of the data is not yet clear, as well as for graphs that represent real-world networks, such as social or computer networks.
Support for global and incremental layout
Tom Sawyer Perspectives offers global graph layout, which calculates positions for all nodes and connectors, routing for edges, and labels for nodes, edges, and connectors.
Tom Sawyer Perspectives also provides incremental layout when you need to maintain your orientation within an existing graph layout. As nodes and edges are added, removed, or moved, incremental layout minimizes changes to object positions, rearranging only those nodes and edges absolutely necessary to result in a readable graph with a clean layout.
Nested graph layout
Graph with expanded node showing nested graph layout capabilities in Tom Sawyer Perspectives.
Connectors
A connector, or port, is a child object of a node that defines the specific location where edges can attach to nodes. Connectors are useful when precision in the graph drawing is critical. For example, connectors are often used in chip or circuit design where users want to represent the physical locations of pins.
Tom Sawyer Perspectives provides options to configure the connector's shape, size, and color. It goes a few steps further by supporting nested connectors, where a connector may have smaller connectors, and connector constraints, where users can choose the node side and sorted ordering of connectors along that side.
The hierarchical and orthogonal layout styles respect the connector constraints when determining node and edge positions. Orthogonal layout integrates connectors even more deeply, giving end users control over connector placement and creating enough space in the drawing for them when needed.
An example Internal Block Definition (IBD) diagram with connectors.
Node and edge labels, and edge decorations
Tom Sawyer Perspectives provides many options to annotate and enhance your graphs to provide the visual cues your users require. In addition to displaying text inside of a node, you can add labels to nodes and edges and control their placement. You can also add decorations to edges, such as an arrowhead along the edge length.
An example graph with edge labels and decorations.
Layout constraints
Tom Sawyer Perspectives supports graph layout constraints, which are additional rules that do not apply to the entire graph, but rather to specific graph objects. For example, you may define that certain nodes should be positioned to the left of a different group of nodes. Or you could define that certain edges attach at specific sides of their end nodes.
Whatever your requirements, Tom Sawyer Perspectives helps you achieve them.
A hierarchical graph layout with vertical alignment constraint (top), and the same graph with orthogonal layout (bottom).
Layout settings
Each layout style included with Tom Sawyer Perspectives offers many options for fine-tuning layout results. Users can adjust spacing between objects, reduce layout post-processing to generate an initial layout more quickly, or define broader properties of the resulting layout. For example, Hierarchical Layout can display a hierarchy from top to bottom or from left to right.
Hierarchical layout with left-to-right curved orthogonal edge routing.
Support for specialized diagram types
Tom Sawyer Perspectives supports several specialized diagram types specific to certain industries or use cases.
Swimlane diagrams
Tom Sawyer Perspectives supports swimlane diagrams, which are especially effective for visualizing process flows. With this layout constraint, the algorithm respects the lanes and automatically places elements into their defined lanes.
Multi-dimensional swimlanes add another level of control by defining both horizontal and vertical lanes, so nodes can be placed within a matrix.
An example multi-dimensional swimlane graph in which process elements are categorized by element type and the day on which it should occur.
One-line diagrams
Using a combination of layout constraints and node and edge customization, Tom Sawyer Perspectives supports one-line diagrams, also referred to as bus-branch model layout.
This graph layout style is used to depict country electrical grids and uses a near-linear-time approach, allowing it to process very large electrical grids.
Timeline diagrams
Tom Sawyer Perspectives supports timeline diagrams where nodes are aligned horizontally by date and where nodes are aligned vertically from bottom to top in sorted order by time of day.
An example timeline diagram.