The Graph Sandwich Problem for P4P4-sparse graphs

The P4P4-sparse Graph Sandwich Problem asks, given two graphs G1=(V,E1)G1=(V,E1) and G2=(V,E2)G2=(V,E2), whether there exists a graph G=(V,E)G=(V,E) such that E1⊆E⊆E2E1⊆E⊆E2 and GG is P4P4-sparse. In this paper we present a polynomial-time algorithm for solving the Graph Sandwich Problem for P4P4-sparse graphs.