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

Family	Algorithm	Description
Basic	`RandomLayout`	Random positions within canvas (baseline/starting point)
Bipartite	`BipartiteLayout`	Two parallel rows for bipartite graphs
Cola	`Layout`	Constraint-based layout with overlap avoidance (port of WebCola)
Force-Directed	`ForceAtlas2Layout`	Continuous layout with adaptive speeds (Gephi algorithm)
	`FruchtermanReingoldLayout`	Classic force-directed with cooling temperature
	`KamadaKawaiLayout`	Stress minimization based on graph-theoretic distances
	`SMACOFLayout`	Stress majorization (Guttman transform); converges more reliably than Kamada-Kawai
	`SpringLayout`	Simple Hooke's law spring forces
	`YifanHuLayout`	Multilevel force-directed for medium-large graphs
Hierarchical	`SugiyamaLayout`	Layered DAG drawing (Sugiyama method)
	`ReingoldTilfordLayout`	Classic tree layout
	`RadialTreeLayout`	Radial tree with root at center
Circular	`CircularLayout`	Nodes arranged on a circle
	`ShellLayout`	Concentric circles by degree or grouping
Spectral	`SpectralLayout`	Laplacian eigenvector embedding
Orthogonal	`KandinskyLayout`	Edges use only horizontal/vertical segments
	`GIOTTOLayout`	Orthogonal drawing for degree-4 planar graphs (opt-in bend-minimal via `bend_optimal`)
Planar	`SchnyderLayout`	Straight-line drawing via Schnyder's realizer on the `(n-1) x (n-1)` grid
	`FPPLayout`	de Fraysseix-Pach-Pollack shift method on the `(2n-4) x (n-2)` grid
	`TutteLayout`	Barycentric (spring) embedding with convex faces for 3-connected planar graphs
	`MixedModelLayout`	Visibility representation: bar-vertices with bendless port-attached edges
	`PlanarizationLayout`	Draws non-planar graphs; crossings become explicit dummy-vertex points

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.

Documentation

The full documentation site is at https://shakfu.github.io/graph-layout, built with MkDocs from docs/:

make docs-serve    # live reload at http://127.0.0.1:8000
make docs          # build into site/
make docs-deploy   # publish to the gh-pages branch

Publishing is manual. .github/workflows/docs.yml holds a strict build that is gated on workflow_dispatch rather than running on every push.

Figures in the docs are generated during the build: a fenced block tagged graph-layout is executed against the installed library and replaced with the resulting inline SVG, so an example that no longer matches the API fails the build rather than leaving a stale image. See docs/embedding-visualizations.md and scripts/mkdocs_hooks.py.

Algorithm Comparison

Algorithm	Best For	Complexity	Features
Random	Baselines, starting points	O(n)	Uniform distribution, reproducible
Bipartite	User-item, author-paper networks	O(n + m)	Auto-detection, crossing minimization
Cola	Constrained layouts, overlap avoidance	O(n^2) per iteration	Constraints, groups, 3D
ForceAtlas2	Large networks, community detection	O(n log n) with Barnes-Hut	Adaptive speed, degree-weighted
Fruchterman-Reingold	General graphs, aesthetics	O(n^2) per iteration	Temperature cooling
Kamada-Kawai	Small-medium graphs, stress minimization	O(n^2) per iteration	Graph-theoretic distances
Spring	Simple layouts, baselines	O(n^2) per iteration	Hooke's law
Yifan Hu	Medium-large graphs (1K-100K nodes)	O(n log n) with Barnes-Hut	Multilevel coarsening, adaptive step
Sugiyama	DAGs, hierarchies	O(n^2)	Layer-based, crossing minimization
Reingold-Tilford	Trees	O(n)	Compact, balanced
Circular	Ring structures, cycles	O(n)	Simple, predictable
Shell	Grouped/stratified data	O(n)	Degree-based grouping
Spectral	Clustering visualization	O(n^3) eigendecomp	Reveals structure
Kandinsky	UML, flowcharts, ER diagrams	O(m²)	Orthogonal edges, bend minimization, compaction, port constraints
GIOTTO	Degree-4 planar graphs	O(m²)	Bend-optimal orthogonal, validates planarity
Schnyder	Compact planar straight-line	O(n²)	Realizer, crossing-free, `(n-1)²` grid
FPP	Planar straight-line	O(n²)	Shift method, crossing-free, `(2n-4)x(n-2)` grid
Tutte	3-connected planar graphs	O(n³) solve	Convex faces, barycentric
Mixed-Model	High-degree planar graphs	O(n²)	Visibility bars, bendless edges, high angular resolution
Planarization	Non-planar graphs	O((n+c)²)	Crossings as explicit dummy vertices

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:

Algorithm	Cython Speedup	Notes
Fruchterman-Reingold	50-60x faster	O(n²) force calculations
ForceAtlas2	15-20x faster	Degree-weighted forces
Yifan Hu	5-7x faster	Multilevel overhead in Python
Shortest paths (Dijkstra)	5x faster	Priority queue operations

Benchmark Results

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

Algorithm	500 nodes	1,000 nodes	5,000 nodes
Random	0.001s	0.002s	0.015s
Circular	0.001s	0.002s	0.015s
Yifan Hu	0.007s	0.014s	0.077s
ForceAtlas2	0.031s	0.066s	0.402s
FR + Barnes-Hut	0.082s	0.188s	1.277s
Spectral	0.036s	0.102s	6.428s
Fruchterman-Reingold	0.059s	--	--
Kamada-Kawai	5.5s	--	--
Kandinsky	0.78s	3.6s	--

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:

Function	Naive	Optimized	Technique
`count_crossings()`	O(m²)	O(m log m)	Merge sort inversion counting
Force repulsion	O(n²)	O(n log n)	Barnes-Hut quadtree
Yifan Hu layout	O(n²)	O(n log n)	Multilevel coarsening + Barnes-Hut

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
make docs          # Build the documentation site

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

Name		Name	Last commit message	Last commit date
.github/workflows		.github/workflows
docs		docs
scripts		scripts
src/graph_layout		src/graph_layout
tests		tests
.gitignore		.gitignore
CHANGELOG.md		CHANGELOG.md
CMakeLists.txt		CMakeLists.txt
LICENSE		LICENSE
Makefile		Makefile
README.md		README.md
TODO.md		TODO.md
mkdocs.yml		mkdocs.yml
mypy-legacy.ini		mypy-legacy.ini
pyproject.toml		pyproject.toml
uv.lock		uv.lock

Latest commit

History

Folders and files

Repository files navigation