Fill-in and operations of graphs (Q1902273)

The fill-in of a graph \(G\), \(f(G)\), is the minimum number of edges that must be added to the graph to make it chordal. In this paper, some properties of the fill-in of graphs are derived. The composite graph of \(G\) for \(H\) is the graph \(G[H]\), obtained from \(G\) by replacing each vertex of \(G\) by an isomorphic copy of \(H\). The paper expresses the fill- in of \(G[H]\), where \(G\) is chordal, in the fill-in of \(H\), the number of connected components of \(G\), and the number of edges of the complement of \(H\). Also, if \(H\) is a complete graph with \(n\) vertices, the fill-in of \(G[H]\) is \(n^2 f(G)\). A strongly planar graph is a graph that does not contain a wheel with four spikes (the graph obtained by making a vertex adjacent to all vertices in a chordless cycle of length four) as a minor. The author observes that every outerplanar graph is strongly planar. One can also observe that every graph of treewidth two is outerplanar. An algorithm that computes the fill-in of strongly planar graphs and that uses \(O(n^2)\) time is given.