=Paper=
{{Paper
|id=Vol-1623/paperco11
|storemode=property
|title=AOE-Trails Constructing for a Plane Connected 4-Regular Graph
|pdfUrl=https://ceur-ws.org/Vol-1623/paperco11.pdf
|volume=Vol-1623
|authors=Tatiana Makarovskikh, Anatoly Panyukov
|dblpUrl=https://dblp.org/rec/conf/door/MakarovskikhP16
}}
==AOE-Trails Constructing for a Plane Connected 4-Regular Graph==
https://ceur-ws.org/Vol-1623/paperco11.pdf
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).