Abstract
We propose a new algorithm, MARINLINGA, for reverse line graph computation—the process of constructing an original graph from its line graph. Unlike previous algorithms that rely on Whitney's isomorphism theorem, MARINLINGA is built on a novel principle of link relabeling and endnode recognition. The algorithm achieves a worst-case complexity of $O(N^2)$, where $N$ is the number of nodes in the line graph. Comparative analysis demonstrates that MARINLINGA is more time-efficient than the well-known Roussopoulos's algorithm, particularly as graph density increases.
Introduction
In graph theory, a line graph $L(G)$ is derived from an original graph $G$ by representing each edge in $G$ as a node in $L(G)$. Two nodes in $L(G)$ are adjacent if their corresponding edges in $G$ share a common vertex. While generating a line graph is computationally trivial, the inverse problem—reconstructing $G$ from $L(G)$—is a complex task with significant applications in social network analysis, community detection, and statistical physics.
Existing solutions, most notably Roussopoulos’s algorithm, typically rely on Whitney’s theorem and involve finding maximal cliques, which can be computationally intensive. We introduce MARINLINGA (MAtrix Relabeling INverse LINe Graph Algorithm), a more direct approach that treats reconstruction as a matrix organization problem.
The MARINLINGA Algorithm
MARINLINGA operates in two primary phases: matrix relabeling and endnode recognition.
Matrix Relabeling
The algorithm begins with the Link Adjacency Matrix (LAM) of the line graph. Through a series of row and column swaps, MARINLINGA reorganizes the LAM to cluster "neighboring" links—those that share a vertex in the original graph. This process creates a structured pattern of 1-entries in the matrix, effectively revealing the underlying connectivity of the original graph without requiring geometric subgraph searches.
Endnode Recognition and Construction
With the matrix organized, the algorithm iteratively assigns vertex IDs to the endpoints of each link. Because the LAM is pre-sorted, the algorithm can deterministically recognize shared vertices based on matrix positions. This sidesteps the need for expensive clique-finding sub-routines, which are often the bottleneck in traditional algorithms.
Key Insights and Forbidden Patterns
A central contribution of this work is the identification of a matrix "signature" for line graphs. If a graph's LAM cannot be relabeled to meet specific criteria, it is not a valid line graph. This allows for early termination in cases where the input is invalid.
The algorithm also utilizes "forbidden link adjacency patterns." These are small graph configurations that, if present as induced subgraphs, disqualify a graph from being a line graph. These serve as a fast "fail-early" check during the reconstruction process.
Performance Evaluation
MARINLINGA was evaluated against Roussopoulos’s algorithm using synthetic Erdős-Rényi random graphs ($G(N, p)$) with node counts up to 350 and link densities ranging from 0.1 to 0.9.
- Complexity: MARINLINGA maintains a worst-case complexity of $O(N^2)$.
- Efficiency: In head-to-head tests, MARINLINGA consistently outperformed the baseline. The performance advantage was most pronounced in dense graphs; for $N=50$ and $p=0.9$, MARINLINGA saved an average of 24.7 milliseconds per reconstruction.
- Robustness: The probability of MARINLINGA being slower than Roussopoulos's algorithm was found to be less than 0.001 across most test configurations.
Conclusion
MARINLINGA represents a shift in reverse line graph construction by moving away from Whitney’s theorem toward a matrix-centric approach. By avoiding NP-complete sub-problems like maximal clique finding, it offers a faster and more scalable solution for large-scale graph analysis. Future work will explore extending this matrix-relabeling logic to directed and weighted graph structures.
Summary updated