Eulerian Cover with Ordered Enclosing for Flat Graphs

Let S be a plane, let G=(V,E) be a flat graph on S, and let f0 be exterior (infinite) face of graph G. Let's consider partial graph J⊂G. Through lnt(J) we shall designate the subset of S which is union of all not containing exterior face f0 connected components of set S\J. We say that route C=v1e1v2e2…vk in a flat graph G has ordered enclosing if for any its initial part C1=v1e1v2e2…el, l⩽|E| the condition Int(Cl)∩E=∅ is hold.The paper presents the algorithm constructing the cover of flat connected graph without end-vertexes by the minimal cardinality sequence of chains with ordered enclosing.The correctness of the constructed algorithm is proved. Computing complexity of the algorithm O(|E|⋅log2|V|).