AOE-Trails Constructing for a Plane Connected 4-Regular Graph Tatiana Makarovskikh and Anatoly Panyukov South Ural State University, pr. Lenina, 76, 454080 Chelyabinsk, Russia Makarovskikh.T.A@susu.ru paniukovav@susu.ru Abstract. 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(|E(G)| log |V (G)|). Keywords: 4-regular graph, A-trail, ordered enclosing, algorithm Introduction 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 sufficient 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 [6]. In common constructing of trail satisfying the given transitions system is N P-hard problem [3]. Its partial case known as a problem of A-trail constructing when transition system for each vertex be a cycle remains N P-hard. Herbert Fleischner determined some classes of graphs for which the polynomail algorithms of finding the A-trail exist. For example, in [1] this problem is solved for outerplanar graphs. 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 [5] is proved. This kind of trail is called as AOE-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 AOE-Trails Constructing for a Plane Connected 4-Regular Graph 63 Fig. 1. Functions representing a plane graph can be interpreted as a claim to avoid the cuts of a part cut off a sheet. The sequence of details cutting is not important in this case. Nevertheless, it is not so in practice. For example, using flame 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 define such a trajectory of cutter that avoids additional cuttings of part cut off a sheet and the next cut off fragment is a neighbouring one. 1 Definitions and Designations 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 ∈ E [5]: – vk (e), k = 1, 2 be vertices incident to edge e, – lk (e), k = 1, 2 be edges got by rotating edge e counter clockwise around vertex v(k), – rk (e), k = 1, 2 be edges got by rotating edge e clockwise around vertex v(k). The illustration of these functions is given on figure 1. Constracting of these functions has no problems. In fact they are defined and used on the stage of graph G design. The space complexity of this representation be O (|E| · log2 |V |). Definition 1. Graph of allowed transitions [3] (or shortly, transitions graph) TG (v) for vertex v ∈ V (G) be a graph which vertices be the edges incident to vertex v, i.e. V (TG (v)) = EG (v), and the set of edges be represented by allowed transitions between edges. Definition 2. System of allowed transitions [2] (or shortly, transitions system) TG be a set {TG (v) | v ∈ V (G) } where TG (v)be transitions graph of vertex v. 64 T. Makarovskikh and A. Panyukov Definition 3. Let P = v0 , e1 , v1 , ..., ek , vk for graph G be TG -compatible if ei , ei+1 ∈ E(TG (vi )) for each i (1 ≤ i ≤ k − 1). The following definition is given in [2]. Definition 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 ∈ V . This order defines the transitions system AG (v) ⊂ O± (v). If ∀v ∈ V (G) AG (v) = O± (v) let transitions system AG (v) be called full transitions system. Definition 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 [2] for which the recog- nition of A-trail existence claims polynomial time. Algorithms for outer-planar graphs [1] and 4-regular graphs [2] are also known. In [2, Corollary VI.6] the proof that A-trail exists for any connected 4-regular graph on any surface is considered. To prove this fact author uses the Splitting lemma. It is also proved that there exists polynomial algorithm for recognition of A-trail for a 4-regular graph. 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 define Int(H) for any subset H ⊂ S as subset of S being the union of all components of set S\H 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 figure 2. The bold arcs show the allowed transitions of this graph. Fig. 2. Example of Eulerian graph Let’s define the condition of ordered enclosing [5] for plane Eulerian graph. AOE-Trails Constructing for a Plane Connected 4-Regular Graph 65 Definition 6. We say that cycle C = v1 e1 v2 e2 . . . vk of Eulerian graph G has ordered enclosing (or being OE-trail for short) if for any its initial part Ci = v1 e1 v2 e2 . . . ei , i ≤ |E(G)| condition Int (Ci ) ∩ G = ∅ holds. Definition 7. We say a trail to be AOE-trail if it is OE-trail and A-trail simultane- ously. Let’s consider trail T1 = e1 e3 e2 e4 e5 e6 of graph on figure 2. This trail is not A-trail but it is OE-trail. Trail T2 = e1 e3 e2 e6 e5 e4 is to be AOE-trail. For example, A-trail T3 = e6 e5 e4 e1 e3 e2 is not OE-trail. We need the following definition for the further considerations and proofs. Definition 8. Let rank of edge e ∈ E(G) be called a value of function rank(e) : E(G) → N recursively defined: – let E1 = {e ∈ E : e ⊂ f0 } be a set of edged bounding outer face f0 of graph G(V, E) then (∀e ∈ E1 ) (rank(e) = 1); – let Ek (G) be a set of edges having rank = 1 k−1 !! [ Gk V, E\ El l=1 then (∀e ∈ Ek ) (rank(e) = k). Definition 9. Partial graph Gk of graph G that E(Gk ) = {e ∈ E(G) : rank(e) ≥ k} be called a partial graph of rank k. Definition 10. The rank of vertex v ∈ V (G) be the value of function rank : V (G) → N: rank(v) = mine∈E(v) rank(e) where E(v) be the set of edges incident to vertex v ∈ V . Definition 11. The rank of face f ∈ F (G) be the value of function rank : F (G) → Z≥0 :  0, if f = f0 , rank(f ) = mine∈E(f ) rank(e), otherwise where E(f ) be the set of edges incident to outer face f ∈ F . The different ways of rank(e) function defining are given in papers [5], [7]. Comput- ing complexity of definition the rank for all graph edges is less than O(|E| log2 |V |). 2 Existence of Transition System Allowing the AOE-Trail 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. 66 T. Makarovskikh and A. Panyukov 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 (figure 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. Fig. 3. Plane graph G (each its vertex has a defined transitions system for A-trail) and corresponding graph G0 being the Jordan curve on a plane 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 = v0 e1 v1 e2 . . . ei , i ≤ |E(G)| the condition Int (Ci ) ∩ G = ∅ holds, i.e. such an A-trail Cn be also an OE-trail. Really, if we consider the existence of edge e ∈ 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 Algorithm for AOE-Trail Constructing 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. AOE-Trails Constructing for a Plane Connected 4-Regular Graph 67 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 ∈ E(G) by functions vs , ls , rs , s = 1, 2 (figure 1); v ∈ 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 define rank(e) for each graph edge e ∈ E(G) and rank(v) for each graph vertex v ∈ V (G). As it was mentioned above the different algorithms of defining rank(e) function are given in papers [5], [7], and their computing complexity is less than O(|E| log2 |V |). The description of Constructing() procedure is given below. Constructing () e = arg maxe∈E(v) rank(e); v = v1 (e); for counter=1 to |E(G)| do { 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); } 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 4- regular graph G so that any its partial graph Gk , k = 1, 2, . . . does not contain cut- vertices. Algorithm runs by time O(|E(G)| · log |V (G)|). 68 T. Makarovskikh and A. Panyukov Proof. Effectiveness of procedures Initiate() and Ranking() is obvious and their total computing complexity is less than O(|E(G)| log |V (G)|). 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 effectiveness of Constructing() procedure. If for the current edge e its vertex v = v2 (e) is visited for the first 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 ∗ ∈ 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 |V (G)| 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 |V (G)|) and the number of iterations is equal to |E(G)|. Hence, computing complexity of algorithm is less than O(|E(G)| log |V (G)|). The algorithm claims rather strict conditions on the graph on absence of cut-vertices for all partial graphs Gk . However, if we ”properly” fix the transitions for all these cut- vertices 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 different pairs of faces (see figure 4). Searching Fig. 4. The correct transition system splitting the cut-vertex in partial graph Gk 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. AOE-Trails Constructing for a Plane Connected 4-Regular Graph 69 These statements truth are obvious. All this allows to suggest the following algorithm. ALGORITHM CUT-POINT-SPLITTING Input: plane connected 4-regular graph G = (V, E) represented for all e ∈ E(G) by functions vs , ls , rs , s = 1, 2 (figure 1). Output: homeomorphic image of graph G = (V, E) with splitted cut-vertices rep- resented for all e ∈ E(G) by functions vs , ls , rs , s = 1, 2. Variables: ∀v ∈ V (G): arrays point(v), rank(v), count(v); ∀f ∈ F (G): array rank(f ). Initiate(): for ∀v ∈ V (G) point(v) = 0; count(v) = 0; Ranking(G); //Function counts ranks of all vertices, edges, and faces Finding(): for ∀e ∈ E(G) do point(v1 (e)) = e; point(v2 (e)) = e; enddo for ∀v ∈ 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 Computing complexity of this algorithm is O(|E(G)| log |V (G)|). Let’s consider the algorithm on example (figure 5). After running CUT-POINT-SPLITTING algorithm we have graph presented on figure 6. Figure 7 shows the homeomorphic image of graph on figure 6. The AOE-trail starting at vertex v1 is v1 v7 v9 v8 v7 v2 v8 v3 v9 v 1 v3 v 2 v1 which corresponds the trail v1 v5 v7 v9 v8 v7 v4 v2 v4 v8 v6 v3 v6 v9 v5 v1 v3 v2 v1 in initial graph. 70 T. Makarovskikh and A. Panyukov Fig. 5. Example of plane 4-regular graph Fig. 6. Graph with splitted cut-vertices Conclusion 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 AOE- trail 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. Fig. 7. Homeomorphic image of graph on fig.6 AOE-Trails Constructing for a Plane Connected 4-Regular Graph 71 References 1. Andersen, L.D., Fleischner, H., Regner, S.: Algorithms and outerplanar conditions for A- trails in plane Eulerian graphs. Discrete Applied Mathematics, no.85, 99–112 (1998). 2. Fleischner, H. Eulerian Graphs and Related Topics, Part 1, Vol.1, Ann. Discrete Mathe- matics, No 45 (1990). 3. Szeider, S. Finding Paths in Graphs Avoiding Forbidden Transitions. Discrete Applied Mathematics. No 126. 261–273 (2003). 4. Makarovskikh, T.A. Covering the rectangular cutting plan by AOE-trails. In: Infornation Technologies and Systems: Proc. of 4-th International conference. Chelyabinsk. Pp. 17–18. (2015) (in Russian). 5. Panyukova, T.A. Trails with ordered enclosing for plane graphs. Discrete Analysis and Operation Research. Part 2. Vol.13, No 2, Pp. 31–43 (2006) (in Russian). 6. Panyukova, T.A. Optimal Eulerian covers for plane graphs. Discrete Analysis and Opera- tion Research. Vol. 18, No 2. Pp. 64–74 (2011) (in Russian). 7. Savitskiy, E.A. Using the Breadth-first Search Algorithm for Definition of Plane Graph Edges Ranks. In: Infornation Technologies and Systems: Proc. of 3-rd International con- ference. Chelyabinsk. Pp.43–45 (2014) (in Russian).