PMI Algorithm — Constructions on Distance Plots
Overview
This repository contains the algorithmic section and proofs for constructing maximum-length PMI sequences on distance plots — the 2D point sets arising from pairwise distance computations on graphs.
It is a technical companion to the main paper PMI-Sequence-Discrete-Math-, focusing on the 2D case and the structured geometry of distance-plot point sets.
Key Observation
Distance plots have a rigid geometric structure imposed by the triangle inequality and metric symmetry. For a graph G, the distance plot is the set of pairs (dist(u,v), dist(v,w)) for all triples u,v,w. This structure — a narrow triangular band — means that arbitrary 2D PMI obstructions (like the forbidden triple {(1,1),(1,4),(4,1)}) are impossible.
This special geometry guarantees that every realizable distance-plot point set admits a PMI sequence of full length |P|, constructible in linear time via a tree traversal.
Main Algorithm
Algorithm: ConstructFullPMI(G, u, v). Given a graph G and a vertex pair (u,v), outputs a PMI sequence of length equal to the number of distinct distances in the distance plot — i.e., a full-length PMI sequence. Runs in O(n) time via a suitably ordered DFS/BFS tree traversal. The key insight is that the 8-connectivity structure of the auxiliary graph H on the distance plot ensures a connected traversal exists.
Structure of This Repo
pmialgo/
├── 2d/
│ ├── driver.tex # Main proof document (algorithms + theorem statements)
│ └── proof1.tex # Full-length PMI construction proof for distance plots
└── scripts/ # Python scripts for diameter-graph generation and plots
Connection to Network Controllability
The distance-based bound on strong structural controllability (from IEEE TAC 2023) requires computing maximum PMI sequence lengths in distance plots. This algorithm provides the efficient construction that underlies those computations.