An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph

1974/10/01 by Philippe G. H. Lehot · 6 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Theory and Algorithms #Graph Labeling and Dimension Problems #Line graph #Graph #Combinatorics #Algorithm #Butterfly graph #Null graph #Complement graph #Strength of a graph #Voltage graph #Graph power #Mathematics #Computer science #Graph bandwidth #Discrete mathematics

paper · pdf · doi:10.1145/321850.321853

openalex publication_date 1974/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21

Abstract

Given a graph H with E edges and N nodes, a graph G is sought such that H is the line graph of G , if G exists. The algorithm does this within the order of E steps, in fact in E + O ( N ) steps. This algorithm is optimal in its complexity.

Citations

• The interchange graph of a finite graph
• Congruent Graphs and the Connectivity of Graphs

Cited by

• Dominoes
• Line graphs of bounded clique-width
• Exact algorithms for maximum independent set
• A labeling algorithm to recognize a line digraph and output its root graph
• The Recognition of Series Parallel Digraphs
• Line graph [wikipedia]