graph-layout - Python Graph Layout Library

A collection of graph layout algorithms in Python.

Written in pure Python with optional Cython acceleration. Prebuilt wheels are published for CPython 3.9-3.14 on Linux (x86_64/aarch64), macOS (Intel/Apple Silicon) and 64-bit Windows, so pip install needs no compiler there. The accelerated module is optional at runtime -- every algorithm falls back to pure Python if it is missing -- but building from the sdist does require a C compiler and CMake, which is what happens on platforms outside that matrix (musllinux/Alpine and 32-bit builds are not published). If you need C++-level performance for large graphs or a more comprehensive graph algorithm and file format toolkit, see the sibling project ogdf-py. For guidance on choosing between the two, see graph-layout vs. ogdf-py.

Layout Algorithms

Installation

# Standard installation (includes Cython extensions for best performance)
pip install graph-layout

# With ILP compaction support (for optimal Kandinsky area minimization)
pip install graph-layout[ilp]

# Development installation
git clone https://github.com/shakfu/graph-layout.git
cd graph-layout
uv sync

Quick Start

Random Layout (Baseline)

Random layout places nodes at random positions. Useful as a baseline for comparing layout quality or as a starting point for iterative algorithms:

from graph_layout import RandomLayout

nodes = [{} for _ in range(10)]
links = [{'source': i, 'target': (i + 1) % 10} for i in range(10)]

layout = RandomLayout(
    nodes=nodes,
    links=links,
    size=(800, 600),
    margin=50,        # Optional padding from edges
    random_seed=42,   # For reproducible layouts
)
layout.run()

for i, node in enumerate(layout.nodes):
    print(f"Node {i}: ({node.x:.1f}, {node.y:.1f})")

Force-Directed Layout

from graph_layout import FruchtermanReingoldLayout

nodes = [{} for _ in range(6)]
links = [
    {'source': 0, 'target': 1},
    {'source': 1, 'target': 2},
    {'source': 2, 'target': 0},
    {'source': 3, 'target': 4},
    {'source': 4, 'target': 5},
    {'source': 2, 'target': 3},
]

layout = FruchtermanReingoldLayout(
    nodes=nodes,
    links=links,
    size=(800, 600),
    iterations=300,
)
layout.run()

for i, node in enumerate(layout.nodes):
    print(f"Node {i}: ({node.x:.1f}, {node.y:.1f})")

ForceAtlas2 Layout

ForceAtlas2 is designed for large network visualization with degree-weighted repulsion and adaptive speeds:

from graph_layout import ForceAtlas2Layout

layout = ForceAtlas2Layout(
    nodes=nodes,
    links=links,
    size=(800, 600),
    scaling=2.0,           # Repulsion strength
    gravity=1.0,           # Pull toward center
    linlog_mode=True,      # Tighter clusters
    strong_gravity_mode=False,  # Distance-based gravity
)
layout.run()

Yifan Hu Multilevel Layout

Yifan Hu is ideal for medium-large graphs (1K-100K nodes) using multilevel coarsening:

from graph_layout import YifanHuLayout

layout = YifanHuLayout(
    nodes=nodes,
    links=links,
    size=(800, 600),
    use_barnes_hut=True,       # O(n log n) approximation
    coarsening_threshold=0.75, # Stop coarsening when ratio > 0.75
    min_coarsest_size=10,      # Minimum nodes in coarsest graph
)
layout.run()

Cola (Constraint-Based) Layout

from graph_layout import ColaLayoutAdapter

nodes = [
    {'x': 0, 'y': 0, 'width': 50, 'height': 30},
    {'x': 100, 'y': 0, 'width': 50, 'height': 30},
    {'x': 200, 'y': 0, 'width': 50, 'height': 30},
]
links = [
    {'source': 0, 'target': 1},
    {'source': 1, 'target': 2},
]

layout = ColaLayoutAdapter(
    nodes=nodes,
    links=links,
    avoid_overlaps=True,
    link_distance=100,
)
layout.run()

Hierarchical Layout (Trees/DAGs)

from graph_layout import SugiyamaLayout

# Tree structure
nodes = [{} for _ in range(7)]
links = [
    {'source': 0, 'target': 1},
    {'source': 0, 'target': 2},
    {'source': 1, 'target': 3},
    {'source': 1, 'target': 4},
    {'source': 2, 'target': 5},
    {'source': 2, 'target': 6},
]

layout = SugiyamaLayout(
    nodes=nodes,
    links=links,
    size=(800, 600),
    layer_separation=80,
    node_separation=50,
)
layout.run()

Circular Layout

from graph_layout import CircularLayout, ShellLayout

nodes = [{} for _ in range(10)]
links = [{'source': i, 'target': (i + 1) % 10} for i in range(10)]

# Simple circular
layout = CircularLayout(nodes=nodes, links=links, size=(800, 600))
layout.run()

# Concentric shells by degree
layout = ShellLayout(nodes=nodes, links=links, size=(800, 600), auto_shells=2)
layout.run()

Spectral Layout

from graph_layout import SpectralLayout

layout = SpectralLayout(
    nodes=nodes,
    links=links,
    size=(800, 600),
    normalized=True,
)
layout.run()

Bipartite Layout

Bipartite layout places nodes in two parallel rows, ideal for user-item networks, author-paper relationships, or any bipartite graph:

from graph_layout import BipartiteLayout

# User-item bipartite graph
nodes = [{} for _ in range(7)]  # 3 users + 4 items
links = [
    {'source': 0, 'target': 3},  # user 0 -> item 3
    {'source': 0, 'target': 4},
    {'source': 1, 'target': 4},
    {'source': 1, 'target': 5},
    {'source': 2, 'target': 5},
    {'source': 2, 'target': 6},
]

layout = BipartiteLayout(
    nodes=nodes,
    links=links,
    size=(800, 600),
    top_set=[0, 1, 2],       # Users on top row
    bottom_set=[3, 4, 5, 6], # Items on bottom row
    minimize_crossings=True, # Reorder to reduce edge crossings
)
layout.run()

# Check if graph is bipartite
print(f"Is bipartite: {layout.is_bipartite}")

# Count edge crossings (O(m log m) using inversion counting)
from graph_layout.bipartite import count_crossings
edges = [(0, 3), (0, 4), (1, 4), (1, 5), (2, 5), (2, 6)]  # Same as links above
crossings = count_crossings(layout.top_nodes, layout.bottom_nodes, edges)
print(f"Edge crossings: {crossings}")

Algorithm insight: Edge crossings in a bipartite drawing equal the number of inversions when edges are sorted by their top-layer position. This allows O(m log m) counting via merge sort instead of O(m²) pairwise comparison—a 188x speedup for 10,000 edges.

Orthogonal Layout (Kandinsky)

Kandinsky layout produces diagrams where all edges use only horizontal and vertical segments. Ideal for UML diagrams, flowcharts, and ER diagrams. Uses a TSM (Topology-Shape-Metrics) approach:

from graph_layout import KandinskyLayout

layout = KandinskyLayout(
    nodes=nodes,
    links=links,
    size=(800, 600),
    node_width=60,
    node_height=40,
    node_separation=60,
    handle_crossings=True,   # Insert crossing vertices for non-planar graphs
    optimize_bends=True,     # Minimize bends using min-cost flow
    compact=True,            # Compact layout to reduce area
    compaction_method="auto", # "auto", "greedy", or "ilp" (ILP requires scipy)
)
layout.run()

# Access edge routing information
for edge in layout.orthogonal_edges:
    print(f"Edge {edge.source}->{edge.target}: {len(edge.bends)} bends")

# Check crossing information
print(f"Edge crossings detected: {layout.num_crossings}")
print(f"Total bends: {layout.total_bends}")

Port Constraints

Specify which side of a node edges should exit/enter from:

from graph_layout import KandinskyLayout
from graph_layout.orthogonal import Side

# Links with explicit port constraints
links = [
    {"source": 0, "target": 1, "source_side": Side.EAST, "target_side": Side.WEST},
    {"source": 1, "target": 2, "source_side": "south", "target_side": "north"},  # Strings work too
    {"source": 2, "target": 3},  # No constraint - uses heuristic
]

layout = KandinskyLayout(nodes=nodes, links=links, size=(800, 600))
layout.run()

# Verify constraints were applied
edge = layout.orthogonal_edges[0]
print(f"Edge exits from: {edge.source_port.side}")  # Side.EAST

GIOTTO Layout (Degree-4 Planar)

GIOTTO produces orthogonal drawings for planar graphs where every node has at most 4 edges (degree <= 4), based on Tamassia's algorithm. Edges are routed heuristically by default; pass bend_optimal=True (below) to draw from the bend-minimal representation:

from graph_layout import GIOTTOLayout

# 3x3 grid graph (degree-4 planar)
nodes = [{} for _ in range(9)]
links = [
    # Horizontal edges
    {"source": 0, "target": 1}, {"source": 1, "target": 2},
    {"source": 3, "target": 4}, {"source": 4, "target": 5},
    {"source": 6, "target": 7}, {"source": 7, "target": 8},
    # Vertical edges
    {"source": 0, "target": 3}, {"source": 1, "target": 4}, {"source": 2, "target": 5},
    {"source": 3, "target": 6}, {"source": 4, "target": 7}, {"source": 5, "target": 8},
]

layout = GIOTTOLayout(
    nodes=nodes,
    links=links,
    size=(800, 600),
    strict=True,  # Raise error if graph doesn't meet requirements
)
layout.run()

print(f"Valid input: {layout.is_valid_input}")
print(f"Total bends: {layout.total_bends}")

Use strict=False to fall back to Kandinsky-like behavior for graphs that don't meet GIOTTO's requirements:

# Graph with degree > 4 - would raise error with strict=True
layout = GIOTTOLayout(nodes=nodes, links=links, strict=False)
layout.run()  # Falls back to Kandinsky-like algorithm

Bend-optimal drawing (bend_optimal)

By default GIOTTO routes edges with a geometric heuristic. Pass bend_optimal=True to instead draw directly from the bend-minimal orthogonal representation (Topology-Shape-Metrics), which dramatically reduces bends — for example a 3x3 grid drops from 24 bends to 0, and K4 from 14 to 4:

layout = GIOTTOLayout(nodes=nodes, links=links, bend_optimal=True)
layout.run()

# Requesting it does not guarantee it is applied: the representation must be a
# realizable orthogonal shape. It works for biconnected, max-degree-4 planar
# graphs whose coordinate assignment is planar; other inputs silently fall back
# to the heuristic router. `used_bend_optimal` reports which path actually ran.
if not layout.used_bend_optimal:
    print("fell back to the heuristic router (not bend-minimal)")

It is opt-in (default off) while the compaction is completed; see docs/rectangularization-plan.md for the remaining work to make it the default.

Planar Straight-Line Layouts

Five algorithms draw a connected planar graph with straight-line edges and no crossings on a compact grid (and one, PlanarizationLayout, extends this to non-planar graphs). They share one substrate — a planar embedding from the LR-planarity test, triangulation to a maximal planar graph, and a canonical ordering — and each falls back to a deterministic circular placement for out-of-domain input, reporting which path ran via a used_* flag.

from graph_layout import SchnyderLayout, FPPLayout, TutteLayout

# A planar graph (square with a diagonal)
nodes = [{} for _ in range(4)]
links = [
    {"source": 0, "target": 1}, {"source": 1, "target": 2},
    {"source": 2, "target": 3}, {"source": 3, "target": 0},
    {"source": 0, "target": 2},
]

layout = SchnyderLayout(nodes=nodes, links=links, size=(800, 600))
layout.run()
print(f"Drew via Schnyder: {layout.used_schnyder}")

• SchnyderLayout — realizer-based drawing; vertex-count barycentric coordinates on the (n-1) x (n-1) grid (Schnyder 1990).

• FPPLayout — de Fraysseix-Pach-Pollack shift method (slope-±1 "tent" over the contour) on the (2n-4) x (n-2) grid.

• TutteLayout — barycentric spring embedding; provably convex faces for 3-connected planar graphs (Tutte 1963).

• MixedModelLayout — Tamassia-Tollis visibility representation: vertices are horizontal bars, edges bendless vertical segments at distinct ports (high angular resolution for high-degree vertices). Exposes vertex_bars and edge_routes.

• PlanarizationLayout — draws non-planar graphs by replacing crossings with dummy vertices, then routing each edge as a polyline through its crossing points. Exposes crossings, crossing_count, and edge_routes.

from graph_layout import PlanarizationLayout

# K5 is non-planar
nodes = [{} for _ in range(5)]
links = [{"source": i, "target": j} for i in range(5) for j in range(i + 1, 5)]

layout = PlanarizationLayout(nodes=nodes, links=links, size=(800, 600))
layout.run()
print(f"Crossings: {layout.crossing_count}")  # 1 for K5

Visualization

Generate visualization images for all algorithms:

uv run python scripts/visualize.py

This creates images in ./build/ showing each algorithm's output.

Algorithm Comparison

Advanced Features

Cola: Overlap Avoidance & Constraints

from graph_layout import ColaLayoutAdapter
from graph_layout.cola.linklengths import SeparationConstraint

# Overlap avoidance
layout = ColaLayoutAdapter(
    nodes=nodes,
    links=links,
    avoid_overlaps=True,
)
layout.run()

# Hierarchical groups
groups = [{'leaves': [0, 1], 'padding': 10}, {'leaves': [2, 3], 'padding': 10}]
layout = ColaLayoutAdapter(
    nodes=nodes,
    links=links,
    groups=groups,
)
layout.run()

# Separation constraints
constraint = SeparationConstraint(axis='x', left=0, right=1, gap=50)
layout = ColaLayoutAdapter(
    nodes=nodes,
    links=links,
    constraints=[constraint],
)
layout.run()

Event System (Animation)

from graph_layout import FruchtermanReingoldLayout
from graph_layout.types import EventType

def on_tick(event):
    print(f"Alpha: {event['alpha']:.3f}")

layout = FruchtermanReingoldLayout(
    nodes=nodes,
    links=links,
    size=(800, 600),
    on_tick=on_tick,
)
layout.run()

# Or register events after construction
layout = FruchtermanReingoldLayout(nodes=nodes, links=links)
layout.on(EventType.tick, on_tick)
layout.run()

3D Layout

from graph_layout.cola import Layout3D, Node3D, Link3D

nodes = [Node3D(0, 0, 0), Node3D(1, 0, 0), Node3D(0, 1, 0)]
links = [Link3D(0, 1), Link3D(1, 2), Link3D(2, 0)]

layout = Layout3D(nodes, links, ideal_link_length=1.0)
layout.start(iterations=100)

Export Formats

All layout classes support exporting to SVG, DOT (Graphviz), and GraphML formats via methods:

from graph_layout import CircularLayout

# Create and run a layout
layout = CircularLayout(
    nodes=[{"index": i} for i in range(5)],
    links=[{"source": i, "target": (i + 1) % 5} for i in range(5)],
    size=(400, 400),
).run()

# Export to SVG (web/print)
svg = layout.to_svg(node_color="#4a90d9", show_labels=True)
with open("graph.svg", "w") as f:
    f.write(svg)

# Export to DOT (Graphviz)
dot = layout.to_dot(directed=False, include_positions=True)
with open("graph.dot", "w") as f:
    f.write(dot)

# Export to GraphML (interchange format)
graphml = layout.to_graphml(include_positions=True)
with open("graph.graphml", "w") as f:
    f.write(graphml)

Orthogonal layouts (KandinskyLayout, GIOTTOLayout) automatically use orthogonal-specific export with rectangular nodes and bend points:

from graph_layout import KandinskyLayout

layout = KandinskyLayout(nodes=nodes, links=links, size=(800, 600)).run()

# SVG with orthogonal edges (polylines with bends)
svg = layout.to_svg()  # Automatically uses orthogonal rendering

# GraphML with bend point data
graphml = layout.to_graphml()  # Includes bend coordinates and port sides

# DOT with splines=ortho
dot = layout.to_dot()  # Uses box nodes and ortho splines

Standalone functions are also available:

from graph_layout import to_svg, to_dot, to_graphml

svg = to_svg(layout, node_color="#ff0000")
dot = to_dot(layout, directed=True)
graphml = to_graphml(layout)

Configuration via Properties

All layout algorithms support configuration via constructor parameters and properties:

from graph_layout import FruchtermanReingoldLayout

# Configure via constructor
layout = FruchtermanReingoldLayout(
    nodes=nodes,
    links=links,
    size=(800, 600),
    iterations=300,
    temperature=100.0,
    cooling_factor=0.95,
)

# Or modify properties after construction
layout = FruchtermanReingoldLayout()
layout.nodes = nodes
layout.links = links
layout.size = (800, 600)
layout.temperature = 50.0
layout.run()

# Access results via properties
for node in layout.nodes:
    print(f"({node.x}, {node.y})")

Module Structure

graph_layout/
    __init__.py              # Top-level exports
    base.py                  # Base classes (BaseLayout, IterativeLayout, StaticLayout)
    types.py                 # Common types (Node, Link, Group, EventType)
    basic/                   # Basic utility layouts
        random.py            # RandomLayout
    bipartite/               # Bipartite layouts
        bipartite.py         # BipartiteLayout
    cola/                    # Constraint-based layout (WebCola port)
        layout.py            # Main 2D layout
        layout3d.py          # 3D layout
        adapter.py           # ColaLayoutAdapter (Pythonic API)
        descent.py           # Gradient descent optimizer
        vpsc.py              # VPSC constraint solver
        ...
    force/                   # Force-directed layouts
        force_atlas2.py
        fruchterman_reingold.py
        kamada_kawai.py
        spring.py
        yifan_hu.py
    hierarchical/            # Tree and DAG layouts
        sugiyama.py
        reingold_tilford.py
        radial_tree.py
    circular/                # Circular layouts
        circular.py
        shell.py
    spectral/                # Spectral methods
        spectral.py
    orthogonal/              # Orthogonal layouts
        kandinsky.py         # Kandinsky layout (arbitrary degree)
        giotto.py            # GIOTTO layout (degree-4 planar, bend-optimal)
        types.py             # NodeBox, Port, OrthogonalEdge, Side
        planarization.py     # Edge crossing detection and vertex insertion
        orthogonalization.py # Bend minimization via min-cost flow
        compaction.py        # Greedy layout area minimization
        compaction_ilp.py    # ILP-based optimal area minimization
    export/                  # Export to various formats
        svg.py               # to_svg, to_svg_orthogonal
        dot.py               # to_dot, to_dot_orthogonal (Graphviz)
        graphml.py           # to_graphml, to_graphml_orthogonal

Performance

Cython Speedups

This project includes a Cython _speedups.pyx module which provides significant speedups over pure Python:

Benchmark Results

Benchmarks on random scale-free graphs (Barabási-Albert model), 50 iterations:

Note: FR and KK use O(n²) and are too slow for graphs >500 nodes without Barnes-Hut. Kandinsky uses O(m²) for edge crossing detection.

Algorithmic Optimizations

Beyond Cython speedups, several algorithms use asymptotically better approaches:

Recommendations by graph size:

• < 500 nodes: Any algorithm works well

• 500-2,000 nodes: Use Yifan Hu, ForceAtlas2, or FR+Barnes-Hut

• > 2,000 nodes: Use Yifan Hu (fastest) or ForceAtlas2 (best for communities)

Barnes-Hut Approximation

ForceAtlas2 and Yifan Hu use Barnes-Hut O(n log n) approximation by default for graphs >50 nodes. For Fruchterman-Reingold, enable it manually:

layout = FruchtermanReingoldLayout(
    nodes=nodes,
    links=links,
    use_barnes_hut=True,
    barnes_hut_theta=0.5,  # 0=exact, higher=faster but less accurate
)

Running Benchmarks

# Generate benchmark graphs
uv run python scripts/generate_benchmark_graphs.py

# Run benchmarks
uv run python scripts/benchmark_layouts.py --graphs "large_*"

Development

make test          # Run tests
make typecheck     # Type checking
make lint          # Lint code
make qa            # Run all qualtiy checks

Related project: ogdf-py

ogdf-py is a sibling project: Python bindings (via nanobind) to the C++ Open Graph Drawing Framework (OGDF). The two overlap heavily -- graph-layout reimplements in pure Python many algorithms OGDF implements in C++ -- and graph-layout's own test suite uses ogdf-py as an independent correctness oracle (tests/test_ogdf_oracle.py) and as a speed baseline (tests/benchmarks/compare_ogdf.py).

Prefer ogdf-py when:

• Scale and speed matter. OGDF is compiled C++. On the identical stress-majorization algorithm it runs ~15-20x faster than graph-layout, and the gap grows with size: at 5000 nodes graph-layout's SMACOF takes ~4.5 minutes versus OGDF's ~16 seconds (see tests/benchmarks/README.md). For graphs beyond ~1000 nodes, or performance-critical pipelines, reach for ogdf-py.

• You need more than layout. OGDF ships a large, mature toolkit graph-layout does not: maximum and minimum-cost flow, matching, Steiner trees, triconnectivity / SPQR-trees, node colouring, and read/write for the GML, GraphML, DOT, GEXF, GDF, and TLP formats.

• You want a battle-tested reference. OGDF is a long-standing framework from the graph-drawing research community.

Prefer graph-layout when:

• Zero native dependency. Pure Python (plus optional Cython); pip install graph-layout needs no C++ toolchain and works on every platform and Python version -- including those where ogdf-py ships no prebuilt wheel (Windows, Python 3.9, 3.14+).

• You want readable, hackable implementations. Every algorithm is Python you can read, modify, and extend -- useful for learning and experimentation.

• You need a layout ogdf-py doesn't expose. Constraint-based layout (Cola: overlap avoidance, separation constraints, groups), ForceAtlas2, and the FPP and mixed-model planar straight-line layouts are graph-layout-only. (Both libraries also do force-directed, hierarchical, orthogonal, and Schnyder/Tutte planar drawing.)

• Throughput on a budget. Not every graph-layout algorithm is slower: its multilevel YifanHu is faster than OGDF's flagship FMMM at every size tested, trading ~20% layout quality for speed.

In short: ogdf-py for C++ performance and algorithmic breadth; graph-layout for a dependency-free, readable, easily-extended pure-Python library with a handful of layout families of its own.

Another earlier graph-drawing sibling project, hola-graph, is a pybind11 wrapper for the adaptagrams HOLA: Human-like Orthogonal Network Layout algorithm by Steve Kieffer, Tim Dwyer, Kim Marriott and Michael Wybrow.

Credits

• Cola: Port of WebCola by Tim Dwyer (see also libcola-releated papers in the adaptagrams project.

• ForceAtlas2: Based on "ForceAtlas2, a Continuous Graph Layout Algorithm for Handy Network Visualization" by Jacomy et al. (2014)

• Fruchterman-Reingold: Based on "Graph Drawing by Force-directed Placement" (1991)

• Kamada-Kawai: Based on "An Algorithm for Drawing General Undirected Graphs" (1989)

• Yifan Hu: Based on "Efficient and High Quality Force-Directed Graph Drawing" (2005)

• Sugiyama: Based on "Methods for Visual Understanding of Hierarchical System Structures" (1981)

• Reingold-Tilford: Based on "Tidier Drawings of Trees" (1981)

• Kandinsky: Based on the Kandinsky model and Tamassia's bend minimization algorithm (1987)

• GIOTTO: Based on Tamassia's "On Embedding a Graph in the Grid with the Minimum Number of Bends" (1987)

License

MIT