k-Plane Graph Drawing Solver

Approximation Algorithms for Minimising k in k-Plane Straight-Line Drawings

see solver_v2.py

OVERVIEW

This repo implements two approximation algorithms for finding straight-line drawings of graphs with minimum k-planarity number $k^*$ (minimum over all drawings of the maximum number of crossings per edge), complemented by a minimax-aware simulated annealing post-processor.

Algorithm 1 – LLL Circular Drawing

• Place vertices on a circle ordered by the Fiedler vector of the graph Laplacian, then refine the circular ordering via swap-based simulated annealing.
• Approximation guarantee: $k \leq m/3 + O(\sqrt{m \log m})$.

Algorithm 2 – Recursive Separator Drawing

• Compute a balanced BFS separator (A, S, B); place S at arc boundaries; assign A and B to opposite arcs recursively.
• Guarantee: $k = O(\Delta \cdot s(n) \cdot \log n)$ where $s(n)$ is separator size.

SA Post-Processing

• Minimax-aware simulated annealing operating directly on vertex positions (off the circle). Crossing counts are maintained incrementally at $O(\Delta \cdot m)$ per move.

Density-Adaptive Time Allocation

• For sparse/medium graphs ($m/n \leq 6$): Fiedler ordering only (~2% of budget), rest to geometric SA.
• For dense graphs ($m/n > 6$): invest ~26% in Fiedler + swap SA, remaining ~72% to geometric SA.
• This split is motivated by experimental evidence that SA alone suffices for sparse graphs, while Fiedler initialisation is critical for dense ones.

REQUIREMENTS

• Python 3.8 or later
• numpy (strongly recommended for spectral ordering)
• scipy (recommended for fast sparse eigensolver at $n \geq 150$)

Install with:

pip install numpy scipy

If scipy is unavailable, the solver falls back to dense numpy eigensolver (slower for $n \geq 150$ but correct). If numpy is unavailable, BFS ordering is used instead of spectral.

FILES

• solver_v2.py — Main solver (all algorithms in one file)
• scaling_experiment.py — Time-scaling experiment runner
• ablation_experiment.py — Component ablation experiment runner
• requirements.txt — Python dependency list
• setup.sh — Environment setup (Linux/macOS)
• setup.bat — Environment setup (Windows)
• setup.py — Package metadata

INPUT/OUTPUT FORMAT

JSON format:

{
  "nodes": [{"id": 0, "x": 0, "y": 0}, ...],
  "edges": [{"source": 0, "target": 1}, ...],
  "width":  W,   // optional; defaults to 1,000,000
  "height": H    // optional; defaults to 1,000,000
}

The solver reads this format and writes the same format with updated (x, y) coordinates for each node.

Output guarantees:

• All coordinates are integers in $[0, W] \times [0, H]$.
• No two vertices share the same coordinate.
• No vertex lies in the interior of any edge.
• Crossings counted pairwise (3 edges at a point = 3 crossings).

USAGE

Basic (combined algorithm, 60-second budget):

python solver_v2.py input.json output.json

With explicit time budget:

python solver_v2.py input.json output.json --time 60

Algorithm configurations (for ablation):

python solver_v2.py input.json output.json --config combined
python solver_v2.py input.json output.json --config circular_only
python solver_v2.py input.json output.json --config circular_sa
python solver_v2.py input.json output.json --config separator_only
python solver_v2.py input.json output.json --config separator_sa
python solver_v2.py input.json output.json --config sa_only

PARAMETERS

• --time T
  Total wall-clock time budget in seconds (default: 55).

• --config C
  Algorithm configuration. Options:

  • combined — density-adaptive, both algorithms + SA. Recommended default.
  • sa_only — random init + full SA budget. Useful as a baseline.
  • circular_only — LLL Circular without SA.
  • circular_sa — LLL Circular + SA.
  • separator_only — Separator Drawing without SA.
  • separator_sa — Separator Drawing + SA.

TIME BUDGET ALLOCATION (combined mode)

Sparse/medium ($m/n \leq 6$):

• 1% separator build ($O(n+m)$, near-instant)
• 2% Fiedler ordering (spectral, no swap SA)
• 0% circular swap SA (skipped entirely)
• 96% geometric SA (all remaining time)

Dense ($m/n > 6$):

• 1% separator build
• 8% Fiedler ordering
• 18% circular swap SA
• 72% geometric SA

EXPERIMENT SCRIPTS

Scaling experiment (k vs. time across multiple budgets):

python scaling_experiment.py --solver solver_v2.py input1.json input2.json ...
# Produces: scaling_results.json

Ablation experiment (k vs. algorithm configuration):

python ablation_experiment.py --solver solver_v2.py --time 60 input1.json ...
# Produces: ablation_results.json

SETUP

Linux / macOS:

chmod +x setup.sh && ./setup.sh
source .venv/bin/activate

Windows:

setup.bat

LICENSE

Python standard library + numpy (BSD) + scipy (BSD).