The polynomial algorithm for constructing a special Eulerian cycle in a plane connected 4-regular graph G = (V; E) is presented in the paper. First of all any cycle of the passed edges does not contain any unpassed edges (the condition of ordered enclosing (OE-cycle). At second, the next edge of this cycle can be chosen from one of two neighbouring edges (left or right) of a cyclic order for the end-vertex of the current edge (the A-trail condition). The computing complexity of this algorithm is O(jE(G)j log jV (G)j).
It is known that with the help of Leonhard Euler's theorem we can easily determine
whether a given graph has Eulerian cycle. In order Eulerian cycle to exist in the graph it
is necessary and su cient that all the vertices of this graph have even degree. However,
the problem of constructing the Eulerian cycle with some restrictions is not too trivial.
For example, for the problem which requires that in a planar Eulerian graph the cycle of
passed edges does not cover unpassed edges (the problem of constructing the OE-trail)
in spite of the polynomial solvability requires a special data organization [
In this paper we consider the case of connected 4-regular plane graphs. The existence
of polynomial time algorithm for constructing the A-trail C being the OE-trail [
The considered problem has its implementation for cutting processes management if it is necessary to take into account some technological restrictions for cutter trajectory. Here the homeomorphic image of a cutting plan be a plane graph usually without separating vertices. For example, the restrictions used for constructing the OE-trail Copyright c by the paper's authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org can be interpreted as a claim to avoid the cuts of a part cut o a sheet. The sequence of details cutting is not important in this case. Nevertheless, it is not so in practice. For example, using ame cutting technology we need absence of cuts intersections. As the model of this problem solution we can consider an A-trail. So, AOE-trail allows de ne such a trajectory of cutter that avoids additional cuttings of part cut o a sheet and the next cut o fragment is a neighbouring one. 1
Let for plane graph G the set E(G) be a set of its edges being the plane Jordan curves
with mutually intersecting entrails homeomorphic to segments. Edge with the same
starting and ending point be called as a loop of graph. Let V (G) be a set of bounding
points of these curves. Topological representation of plane graph G = (V; E) on plane
S up to homeomorphism can be determined by the following functions for each edge
e 2 E [
De nition 1. Graph of allowed transitions [
De nition 2. System of allowed transitions [
fTG(v) j v 2 V (G) g where TG(v)be transitions graph of vertex v. De nition 3. Let P = v0; e1; v1; :::; ek; vk for graph G be TG-compatible if ei; ei+1 2 E(TG(vi)) for each i (1 i k 1).
De nition 4. Let for Eulerian trail
T = v0; k1; v1; : : : ; kn; vn; vn = v0 in graph G = (V; E) the cyclic order O (v) is given for each vertex v 2 V . This order de nes the transitions system AG(v) O (v). If 8v 2 V (G) AG(v) = O (v) let transitions system AG(v) be called full transitions system.
De nition 5. Eulerian AG-compatible trail T be called A-trail Hence the sequent edges of trail T (incident to vertex v) be the neighbours in cyclic order O (v).
As it was mentioned above there are some classes of graphs [
Let's consider the plane S. Let plane Eulerian graph G = (V; E) be set on this plane. Let f0 be the outer face of graph G. Let's de ne Int(H) for any subset H S as subset of S being the union of all components of set SnH without outer face f0. So, Int(G) be the union of all inner faces of graph G.
We take the neighbours of edge e got after rotating this edge clockwise and counter clockwise in vertex v as sequence of edges in O (v) for plane graph.
Let's consider graph on gure 2. The bold arcs show the allowed transitions of this
graph.
Let's de ne the condition of ordered enclosing [
Gk
V; En k 1 [ El l=1 !! then (8e 2 Ek) (rank(e) = k).
De nition 9. Partial graph Gk of graph G that E(Gk) = fe 2 E(G) : rank(e) be called a partial graph of rank k. kg De nition 10. The rank of vertex v 2 V (G) be the value of function rank : V (G) ! N: rank(v) = mine2E(v) rank(e) where E(v) be the set of edges incident to vertex v 2 V . De nition 11. The rank of face f 2 F (G) be the value of function rank : F (G) ! Z 0: rank(f ) = 0; if f = f0; mine2E(f) rank(e); otherwise where E(f ) be the set of edges incident to outer face f 2 F .
The di erent ways of rank(e) function de ning are given in papers [
A trail for which the condition of ordered enclosing is vanished always has a transition through the enclosing cycle. This transition is not compatible with the transitions system for A-trail. On the other hand the following theorem holds. Theorem 1. If there is an A-trail for a plane graph G then there is also an AOE-trail. Proof. A-trail for a plane Eulerian graph is to be the closed Jordan curve without self-intersections. This curve may be got by the following way. Let's consider graph G, there is a transition system for each vertex corresponding the A-trail. Let graph G0 is obtained of graph G by splitting the vertices according to the system of allowed transitions ( gure 3). Graph G0 obtained this way represents a Jordan curve without intersections and according to Jordan theorem this curve splits the plane into outer and inner components.
Obviously, there exists vertex v0 on the curve obtained incident to outer face of graph G and to edge en: rank(en) = 1. If v0 be taken as beginning of AOE-trail and the direction of passing is chosen so that edge (en) be the end of trail Cn than due to absence of intersections for the inner set of any initial part of a trail Ci = v0e1v1e2 : : : ei, i jE(G)j the condition holds, i.e. such an A-trail Cn be also an OE-trail. Really, if we consider the existence of edge e 2 Int (Ci) then we get a contradiction to absence of intersections in transition system.
Theorem 2. There is an AOE-trail for plane connected 4-regular graph G. Proof. The proof of A-trail existence for a connected 4-regular graph is given in [2, Corollary VI.6]. As this graph contains an A-trail then due to theorem 1 there is also an AOE-trail. 3
Let's consider the algorithm for constructing AOE-trail for plane connected 4-regular graph. Let's input and output data be the global variables for shortness of exposition. ALGORITHM AOE-TRAIL
Input: plane connected 4-regular graph G = (V; E) without cut-vertices for partial graph Gk, k = 1; 2; : : : represented for all e 2 E(G) by functions vs; ls; rs , s = 1; 2 ( gure 1); v 2 V (f0) be starting vertex.
Output:
AT rail be the output-stream,
containing the AOE-trail constructed by algorithm.
Initiate(G); Ranking(G); Constructing(); End of algorithm
The (Initiate()) procedure initializes by value 0 the counter of edges included to a resulting trail, and also assigning to all edges the mark true corresponding the unpassed edge.
The functional purpose of the procedure Ranking() is to de ne rank(e) for each
graph edge e 2 E(G) and rank(v) for each graph vertex v 2 V (G). As it was mentioned
above the di erent algorithms of de ning rank(e) function are given in papers [
The description of Constructing() procedure is given below.
Constructing () e = arg maxe2E(v) rank(e); v = v1(e); for counter=1 to jE(G)j do f if (v 6= v1(e)) REPLACE(e); AT rail << v << e; mark(e) = false; counter++; v = v2(e); if (rank(r2(e)) > rank(l2(e))) then
if mark(r2(e)) then e = r2(e) else e = l2(e); else if mark(l2(e)) then e = l2(e) else e = r2(e); g End of Procedure
While running procedure Constructing (e) the interchange of numbers of incident to e vertices appear, so that vertex v1(e) should be passed earlier than vertex v2(e). This procedure is realized as the following.
Procedure REPLACE ( Edge ) tmp1 = v2(Edge); tmp2 = l2(Edge); tmp3 = r2(Edge); v2(Edge) = v1(Edge); l2(Edge) = l1(Edge); r2(Edge) = r1(Edge); v1(Edge) = tmp1; l2(Edge) = tmp2; r2(Edge) = tmp3; End of Procedure
The following theorem holds.
Theorem 3. Algorithm AOE-TRAIL constructs AOE-trail for a plane connected 4regular graph G so that any its partial graph Gk, k = 1; 2; : : : does not contain cutvertices. Algorithm runs by time O(jE(G)j log jV (G)j). Proof. E ectiveness of procedures Initiate() and Ranking() is obvious and their total computing complexity is less than O(jE(G)j log jV (G)j).
The main cycle of procedure Constructing() is in choosing the next unpassed edge e incident to vertex v2(e) maximal rank. This procedure is run until all the edges are not included to the resulting trail (their mark will be changed to false).
Let's prove the e ectiveness of Constructing() procedure. If for the current edge e its vertex v = v2(e) is visited for the rst time then running of body of the cycle may be interpreted as splitting the vertex v = v2(e) according to the system of transitions of A-trail.
After such a splitting the homeomorphic image of the graph obtained does not contain the vertex v . On the second visit to vertex v 2 V (G) algorithm continues forming the trail according to homeomorphic image of graph obtained earlier.
The homeomorphic image of obtained graph be a plane connected graph after each running of the cycle body since any partial graph of rank k contains no cut-vertices.
After running of jV (G)j splits the resulting homeomorphic image of graph be a circle obtained by splitting the vertices according to the transitions system of A-trail. Wherein the stream AT rail contains the resulting AOE-trail.
As homeomorphic image remains connected then all edges are treated by algorithm (i.e. have mark false). Procedure Constructing() has the only cycle. Computing complexity of cycle body is less than O(log jV (G)j) and the number of iterations is equal to jE(G)j. Hence, computing complexity of algorithm is less than O(jE(G)j log jV (G)j).
The algorithm claims rather strict conditions on the graph on absence of cut-vertices for all partial graphs Gk. However, if we "properly" x the transitions for all these cutvertices then as the result of splitting we get a graph for which any partial graph does not contain any cut-vertices. The correct transition is one between the arcs satisfying cyclic transition system and incident to di erent pairs of faces (see gure 4). Searching of cut-vertices uses the following propertioes of 4-regular graphs.
Proposition 1. Vertex incidence to four edges bounding outer face is cut-vertex. Proposition 2. Outer face of Gk is a union of all faces of rank k for graph G.
ALGORITHM CUT-POINT-SPLITTING
Input: plane connected 4-regular graph G = (V; E) represented for all e 2 E(G) by functions vs; ls; rs , s = 1; 2 ( gure 1).
Output: homeomorphic image of graph G = (V; E) with splitted cut-vertices represented for all e 2 E(G) by functions vs; ls; rs , s = 1; 2.
Variables: 8v 2 V (G): arrays point(v), rank(v), count(v); 8f 2 F (G): array rank(f ).
Initiate(): for 8v 2 V (G) point(v) = 0; count(v) = 0; Ranking(G); //Function counts ranks of all vertices, edges, and faces Finding(): for 8e 2 E(G) do
point(v1(e)) = e; point(v2(e)) = e; enddo for 8v 2 V (G) do e = point(v); k = rank(v); if (v = v1(e)) then s = 1 else s = 2; e = ls(e); if (rank(e) = k) then count(v) = count(v) + 1, e = ls(e); if (rank(e) = k) then count(v) = count(v) + 1, e = ls(e); if (rank(e) = k) then count(v) = count(v) + 1, if (count(v) = 4) then if ((fs(e) = fs(ls(e)) and f3 s(e) = f3 s(ls(e))) or
(fs(e) = f3 s(ls(e)) and f3 s(e) = fs(ls(e)))) then e = ls(e), ls(e) = rs(e), rs(rs(e)) = e, rs(e ) = ls(e ), ls(ls(e )) = e ; else e = rs(e), rs(e) = ls(e), ls(ls(e) = e, ls(e ) = rs(e ), rs(rs(e )) = e ; endfor
End of algorithm 6.
Computing complexity of this algorithm is O(jE(G)j log jV (G)j).
Let's consider the algorithm on example ( gure 5).
After running CUT-POINT-SPLITTING algorithm we have graph presented on gure which corresponds the trail in initial graph.
Hence, any A-trail for a plane graph up to choosing the start vertex and routing direction is to be an AOE-trail. It is possible to construct Eulerian cycle being AOEtrail for plane 4-regular graph by presented algorithm. For graphs with vertices of degree greater than 4 this algorithm may not construct any AOE-trail. Further interest are algorithms for constructing AOE-trails for arbitrary plane connected Eulerian graph. Acknowledgments. The authors thank professor of TU Vienna Herbert Fleischner for statement and productive discussion of the problem.