Reverse Line Graph Construction: The Matrix Relabeling Algorithm MARINLINGA Versus Roussopoulos's Algorithm

D. Liu, Stojan Trajanovski, Piet Van MieghemarXiv 2010 · DOI · arXiv

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.

Figure 4: A forbidden link adjacency pattern used by MARINLINGA to identify invalid line graphs.

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.

Figure 6: Another example of a forbidden pattern; the absence or presence of specific edges in these configurations serves as a diagnostic tool.

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

Abstract

We propose a new algorithm MARINLINGA for reverse line graph computation, i.e., constructing the original graph from a given line graph. Based on the completely new and simpler principle of link relabeling and endnode recognition, MARINLINGA does not rely on Whitney's theorem while all previous algorithms do. MARINLINGA has a worst case complexity of O(N^2), where N denotes the number of nodes of the line graph. We demonstrate that MARINLINGA is more time-efficient compared to Roussopoulos's algorithm, which is well-known for its efficiency.
BibTeX
@misc{liu2010reverse,
  author = {D. Liu and Stojan Trajanovski and Piet Van Mieghem},
  title = {{Reverse Line Graph Construction: The Matrix Relabeling Algorithm MARINLINGA Versus Roussopoulos's Algorithm}},
  year = {2010},
  eprint = {1005.0943},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1005.0943},
}
Figure