Linearly Synthesizing 2-Connected Simplicial Graphs
Jianer Chen, Jonathan L. Gross · 1995
It is proved that for any two 2-connected, smooth, and simplicial graphs G and H such that H is homeomorphic to a subgraph of G, there is a sequence of 2-connected subgraphs G 0 ` G 1 ` \\Delta \\Delta \\Delta ` G r = G of G such that G 0 is homeomorphic to the graph H , each G i is obtained from G i\\Gamma1 by adding a chain, 1 i r, and for any two consecutive graphs in the sequence, at least one is homeomorphic to a smooth and simplicial graph. Our result has found applications in the study of graph imbeddings on topological surfaces and in designing efficient graph algorithms.