The problem of constructing
the maximal planar subgraph of a non-planar graph is a common task in the graph
visual construction. It was demonstrated in [1] that the problem of constructing
a maximal planar subgraph of a non-planar graph is NP-complete. Thus, it can be
solved by a restricted class of brute force search algorithms and there is no
polynomial algorithm for its solvability.
We will further consider
an approximate solution to the problem in a general form, without dwelling on
the details of methods and algorithms, but highlighting the main stages. To
solve the problem, we will follow the principles of diakoptics [2], that is, we
divide the solution into interconnected parts.
Let us consider the graph
G
= (
V
,
E
) with a numbered set of edges
E
= {
e
1
,
e
2
,...,
e
m
}
and a numbered set of vertices
V
= {
v
1
,
v
2
,...,
v
n
},
wherein card(
V
)
=
n
and card(
E
)
=
m
. Next, lets select the nonseparable
part of the graph.
Definition 1.
By a
nonseparable
graph
G
, we mean a connected undirected graph without loops and
multiple edges, without bridges and articulation points (cut vertices), in
which the degree of each vertex is more than two.
Thus, diakoptics allows
applying a mathematical model based on the cyclomatic properties of a graph, and
thereby connect MacLanes theorem to the solution of the problem. Then the solution
process can be represented as consisting of the following two successive
stages:
ท
constructing
a maximal planar subgraph for a nonseparable subgraph;
ท
adding
unit edges to the solution until obtaining a separable maximal planar subgraph
(even with no additional edges).
In such a model, the major
role is played by graph simple cycles. Therefore, the problem of constructing a
maximal planar subgraph can be reduced to the combinatorial optimization problem.
Combinatorial optimization
problem:
on
the set of simple cycles, find a subset of independent cycles, which represents
a planar subgraph and satisfies a zero value of MacLane functional and Euler's
equation with the maximum number of edges.
Such a problem statement
allows treating the enumeration problem as a representative of the class of
combinatorial optimization problems. Hence, the well-developed mathematical framework
of discrete optimization can be applied to solve the problem. In addition, the
cyclomatic approach allows strictly and unambiguously describing the
topological drawing of the planar part of a graph, since the independent system
of cycles obtained as a result of the solution induces (generates) the rotation
of graph vertices. Indeed, according to the theory of rotations, the rotation
of vertices creates a topological drawing of a graph [3].
Definition 2.
An
isometric cycle
in a graph is a simple cycle for which the shortest path between any two of its
vertices consists of the edges belonging to this cycle.
An isometric cycle is essentially
a special case of an isometric subgraph [4].
In other words, an
isometric cycle in a graph G is a subgraph
in the form of a simple
cycle, where between any two non-adjacent vertices of the given subgraph in the
graph G there are no paths of shorter length, than the paths belonging to this
cycle.
We will search of a
solution on the set of graph isometric cycles. The set of isometric cycles of a
graph is a matroid [5].
Definition 3.
A
matroid
M is a
finite set
S
and a set
F
of subsets of
S
such that the following conditions, called independence conditions, are
satisfied:
|
Æ
Î
F
|
(1)
|
|
If
Z
Î
F
and Y
Í
Z
,
then
Y
Î
F
|
(2)
|
|
If Z
and Y are members
of
F
and
½
Z
½
=
½
Y
½
+1, then
exists such
z
Î
Z
Y,
that Y
È
z
Î
F
|
(3)
|
In expression (3), subtracting Z Y is understood
as Z / (Z
Ç
Y). Elements of the set S are
called
elements
of the matroid M. Members of the set
F
are called
sets
of the matroid
M. The maximal as for inclusion independent set of the matroid M is called the
base
of the matroid M. The set of bases of the matroid M is denoted by
B
(M) or simply
B
.
A subset S that does not belong to the set
F
is called
dependent
. The minimal
as for inclusion dependent subset S is called the
cycle
of the matroid
M. The set of cycles of the matroid M is denoted by
(M) or simply
.
Let us further denote the set of graph isometric cycles by
. In
turn, the set of matroid bases of isometric cycles will be denoted by
.
The basis of the linear subspace of cycles consisting of isometric cycles of
cardinality equal to the cyclomatic number of the graph
will be
denoted as
and called the
configuration
.
In turn,
, where
is a set of
configurations. It is natural to assume that
.
A set of configurations can be represented as a structural number
W
,
where each column (element) characterizes the configuration. On the other hand,
a structural number can be represented as a product of single-line structural
numbers characterizing isometric cycles passing along a selected chord.
Moreover, according to the rules of the structural numbers algebra [6], the selection
of a graph tree does not affect the final result.
In turn, a subset of cycles can be associated with two vectors: the
vector of cycles along the edges
P
e
,
which determines the number of isometric cycles passing along the edges of the
given subset, and the vector of cycles passing through the vertices
P
v
, which determines the number of
isometric cycles passing through the vertices of a given subset.
The planar
part of a non-planar graph must satisfy a zero value of the MacLane functional [7]
:
|
|
(4)
|
where a
i
are coefficients of the vector P
e
.
Configuration
requirements:
1. The configuration
should be linearly independent.
2. The
value of the MacLane functional for the configuration should tend to the
minimum value.
3. There
should be no zero elements in the vector of cycles along the edges for the
configuration.
4. The
vector of cycles along the edges for the configuration must necessarily contain
single elements.
5. There
should be no zero elements in the vector of cycles through vertices for the configuration.
Obviously,
the value of the MacLane functional for the configuration of a non-planar graph
is greater than zero. Therefore, in order to achieve a zero value of the
MacLane functional, it is necessary to remove some part of the cycles. We can
use the operation of differentiating the structural number
W
of
isometric cycles [8, 9] to model the the process of removing cycles by the gradient
descent method.
We
illustrate the process of constructing the planar part of a non-planar
nonseparable graph with specific examples, as during explanation it is
necessary to introduce new non-conventional terms and definitions. Lets
consider the foregoing by the example of the following undirected graph.
Fig. 1. Graph G.
The number of isometric cycles of the graph is 20. They are
distributed according to lengths as follows: lengths 413 cycles, lengths 67
cycles.
The cycles of the corresponding matroid
(
)
consist of 6 sets, each
containing 3 isometric cycles, as well as of 2 sets containing 4 cycles, and so
on.
As an example, consider one of the matroid cycles shown in Fig. 2:
Fig. 2.
A topological drawing of the 18
th
cycle of the matroid.
c
18
c
17
c
14
c
1
c
7
c
9
c
15
= {
e
14
,
e
15
,
e
20
,
e
22
}
{
e
12
,
e
15
,
e
18
,
e
19
}
{
e
1
,
e
2
,
e
9
,
e
10
,
e
12
,
e
14
}
{e
1
,e
2
,e
4
,e
5
}
{
e
4
,
e
7
,
e
9
,
e
11
}
{
e
5
,
e
7
,
e
18
,
e
19
,
e
21
,
e
22
}
{e
10
,e
11
,e
20
,e
21
}
=
If we remove the following cycles from the set of
isometric cycles: {
๑
6
,
๑
9
,
๑
14
,
๑
12
,
๑
16
,
๑
13
}, then we get the element of the matroid base consisting of
14 cycles.
The set of independent cycles belonging to the
selected element of the matroid base will be further called the
truncated
set of isometric cycles
. In turn, truncated sets of isometric cycles form
the base of the matroid.
Next, we form single-line structural numbers for a
truncated set of isometric cycles. For the selected graph tree T = {e
1
,e
4
,e
5
,e
8
,e
10
,e
12
,e
13
,e
17
,e
19
,e
20
,e
21
,e
22
}
the set of chords is as follows: H = {e
2
,e
3
,e
6
,e
7
,e
9
,e
11
,e
14
,e
15
,e
16
,e
18
}.
And then for the set of isometric cycles, single-line structural numbers have
the following form:
the cycles passing
through the chord e
2
: [c
1
,c
4
,c
5
,c
14
];
the cycles passing
through the chord e
3
: [c
2
,c
3
,c
4
,c
5
];
the cycles passing
through the chord e
6
: [c
6
,c
8
,c
10
,c
20
];
the cycles passing
through the chord e
7
: [c
7
,c
9
,c
10
,c
11
,c
12
,c
20
];
the cycles passing
through the chord e
9
: [c
2
,c
3
,c
6
,c
7
,c
14
];
the cycles passing
through the chord e
11
: [c
7
,c
10
,c
15
];
the cycles passing
through the chord e
14
: [c
3
,c
12
,c
13
,c
14
,c
18
];
the cycles passing
through the chord e
15
: [c
11
,c
17
,c
18
,c
19
,c
20
];
the cycles passing
through the chord e
16
: [c
2
,c
3
,c
4
,c
16
,c
19
];
the cycles passing
through the chord e
18
: [c
5
,c
9
,c
16
,c
17
].
We construct single-line structural
numbers for a truncated set of isometric cycles. The length of an element of a
structural number is always equal to the number of chords in the graph, in this
case, ten.
Using the line search algorithm, we select the
entire set of elements of the truncated structural number
W
and compute
their number. The quantity of structural number elements for our example is
594.
Truncated
single-line structural numbers:
the cycles passing
through the chord e
14
: [c
3
,c
18
];
the cycles passing
through the chord e
18
: [c
5
,c
17
];
the cycles passing
through the chord e
2
: [c
1
,c
4
,c
5
];
the cycles
passing through the chord e
6
: [c
8
,c
10
,c
20
];
the cycles
passing through the chord e
9
: [c
2
,c
3
,c
7
];
the cycles
passing through the chord e
11
: [c
7
,c
10
,c
15
];
the cycles
passing through the chord e
3
: [c
2
,c
3
,c
4
,c
5
];
the cycles
passing through the chord e
7
: [c
7
,c
10
,c
11
,c
20
];
the cycles
passing through the chord e
16
: [c
2
,c
3
,c
4
,c
19
];
the
cycles passing through the chord e
15
: [c
11
,c
17
,c
18
,c
19
,c
20
];
Elements
of a truncated structural number (configuration) have the form (e.g., consider
the 172
nd
and 173
rd
elements):
172
nd
element {c
3
,c
5
,c
1
,c
20
,c
7
,c
10
,c
2
,c
11
,c
4
,c
18
};
173
rd
element {c
3
,c
5
,c
1
,c
20
,c
7
,c
10
,c
2
,c
11
,c
4
,c
19
};
.
Approximately the quantity
of structural number elements can be calculated by the formula
:
|
|
(5)
|
where
k
u
is the cardinality
of a truncated set of isometric cycles.
Naturally, the Monte Carlo
method should be used for creating practical systems of approximate solutions
for isolating the planar part of a non-planar graph,. That is, using gradient
descent method, randomly select a large number of configurations. Then, select
the appropriate solution using the MacLane functional as the objective function
and formalizing the process as taking the inverse derivative of the structural
number.
The following conditions
must be observed for the planar part of configuration:
1.
When
the cycle is excluded from the configuration (or when the operation of
structural number differentiation is applied), the PontryaginKuratowski
functional should be used as the objective function.
2.
When
excluding cycles from the configuration, the rule must be fulfilled: when
excluding one cycle, one and only one edge must be removed.
3.
As a
result of the exclusion of cycles, a subsystem of cycles should be formed that
has a zero value of the PontryaginKuratowski functional. Such a subsystem is
called a
planar configuration
.
In turn, a planar
configuration must satisfy a number of requirements:
1.
For a planar
configuration, the Euler's law must be satisfied.
2.
A
linear combination of cycles of a planar configuration must necessarily form a
rim that characterizes a non-empty connected simple cycle.
3.
The
determined subgraph should be connected and should not contain articulation
points.
4.
The
cycles of a planar configuration should induce the rotation of vertices, which
describes the topological drawing of the planar part of a graph.
By randomly generating configurations using the gradient
descent method, we obtain the following planar configurations:
Table 3.1. Planar configuration 1
|
|
The set of graph cycles in the form of edges:
|
The set of graph cycles in the form of vertices:
|
The tuple of isometric cycles vertices:
|
|
๑
16
|
{e
12
,e
16
,e
17
,e
18
}
|
{v
9
,v
5
,v
11
,v
4
}
|
<
v
9
,v
5
,v
11
,v
4
>
|
|
c
1
|
{e
1
,e
2
,e
4
,e
5
}
|
{v
7
,v
2
,v
9
,v
1
}
|
<
v
1
,v
9
,v
2
,v
7
>
|
|
๑
6
|
{e
4
,e
6
,e
8
,e
9
}
|
{v
7
,v
3
,v
8
,v
2
}
|
<
v
2
,v
8
,v
3
,v
7
>
|
|
๑
8
|
{e
5
,e
6
,e
12
,e
13
}
|
{v
9
,v
4
,v
8
,v
2
}
|
<
v
9
,v
4
,v
8
,v
2
>
|
|
๑
18
|
{e
14
,e
15
,e
20
,e
22
}
|
{v
13
,v
6
,v
12
,v
4
}
|
<
v
4
,v
12
,v
6
,v
13
>
|
|
๑
15
|
{e
10
,e
11
,e
20
,e
21
}
|
{v
13
,v
6
,v
10
,v
3
}
|
<
v
13
,v
6
,v
10
,v
3
>
|
|
๑
5
|
{e
2
,e
3
,e
17
,e
18
}
|
{v
9
,v
5
,v
11
,v
1
}
|
<
v
1
,v
11
,v
5
,v
9
>
|
|
๑
13
|
{e
8
,e
10
,e
13
,e
14
}
|
{v
8
,v
4
,v
13
,v
3
}
|
<
v
8
,v
4
,v
13
,v
3
>
|
|
rim
|
{e
16
,e
1
,e
9
,e
15
,e
22
,e
11
,e
21
,e
3
}
|
{v
11
,v
1
,v
7
,v
3
,v
10
,v
6
,v
12
,v
4
}
|
<
v
11
,v
1
,v
7
,v
3
,v
10
,v
6
,v
12
,v
4
>
|
Fig. 3.
Topological drawing of the planar configuration 1.
During planarization the edges
ๅ
7
and
ๅ
19
were removed.
Vertices rotation of the plane graph:
rotation of the vertex
v
1
:
v
11
v
7
v
9
v
11
rotation of the vertex
v
2
:
v
8
v
9
v
7
v
8
rotation of the vertex
v
3
:
v
7
v
10
v
11
rotation of the vertex
v
4
:
v
11
v
9
v
8
v
13
rotation of the vertex
v
5
:
v
9
v
11
v
9
rotation of the vertex
v
6
:
v
13
v
10
v
13
rotation of the vertex
v
7
:
v
1
v
3
v
2
v
1
rotation of the vertex
v
8
:
v
4
v
2
v
3
v
4
rotation of the vertex
v
9
:
v
4
v
5
v
1
v
2
v
4
rotation of the vertex
v
10
:
v
3
v
6
v
3
rotation of the vertex
v
11
:
v
5
v
4
v
1
v
5
rotation of the vertex
v
12
:
v
4
v
6
v
4
rotation of the vertex
v
13
:
v
4
v
3
v
6
v
4
Table 3.2. Planar configuration 2.
|
|
The set of graph cycles in the form of edges:
|
The set of graph cycles in the form of vertices:
|
The tuple of isometric cycles vertices:
|
|
๑
15
|
{e
10
,e
11
,e
20
,e
21
}
|
{v
13
,v
6
,v
10
,v
3
}
|
<
v
13
,v
6
,v
10
,v
3
>
|
|
๑
8
|
{e
5
,e
6
,e
12
,e
13
}
|
{v
9
,v
4
,v
8
,v
2
}
|
<
v
9
,v
4
,v
8
,v
2
>
|
|
๑
16
|
{e
12
,e
16
,e
17
,e
18
}
|
{v
9
,v
5
,v
11
,v
4
}
|
<
v
9
,v
5
,v
11
,v
4
>
|
|
๑
13
|
{e
8
,e
10
,e
13
,e
14
}
|
{v
8
,v
4
,v
13
,v
3
}
|
<
v
8
,v
4
,v
13
,v
3
>
|
|
๑
5
|
{e
2
,e
3
,e
17
,e
18
}
|
{v
9
,v
5
,v
11
,v
1
}
|
<
v
1
,v
11
,v
5
,v
9
>
|
|
๑
6
|
{e
4
,e
6
,e
8
,e
9
}
|
{v
7
,v
3
,v
8
,v
2
}
|
<
v
2
,v
8
,v
3
,v
7
>
|
|
๑
18
|
{e
14
,e
15
,e
20
,e
22
}
|
{v
13
,v
6
,v
12
,v
4
}
|
<
v
4
,v
12
,v
6
,v
13
>
|
|
๑
7
|
{e
4
,e
7
,e
9
,e
11
}
|
{v
7
,v
3
,v
10
,v
2
}
|
<
v
7
,v
3
,v
10
,v
2
>
|
|
rim
|
{e
21
,e
5
,e
16
,e
2
,e
3
,e
15
,e
22
,e
7
}
|
{v
10
,v
2
,v
9
,v
1
,v
11
,v
4
,v
12
,v
6
}
|
<
v
6
,v
12
,v
4
,v
11
,v
1
,v
9
,v
2
,v
10
>
|
Fig. 4.
Planar
configuration
2.
During planarization the edges
ๅ
1
and
ๅ
19
were removed.
Vertices
rotation of the plane graph:
rotation of the vertex
v
1
:
v
11
v
9
v
11
rotation of the vertex
v
2
:
v
10
v
7
v
8
v
9
v
10
rotation of the vertex
v
3
:
v
10
v
13
v
8
v
7
v
10
rotation of the vertex
v
4
:
v
8
v
13
v
12
v
11
v
9
v
8
rotation of the vertex
v
5
:
v
9
v
11
v
9
rotation of the vertex
v
6
:
v
13
v
10
v
12
v
13
rotation of the vertex
v
7
:
v
2
v
3
v
2
rotation of the vertex
v
8
:
v
3
v
4
v
2
v
3
rotation of the vertex
v
9
:
v
1
v
2
v
4
v
5
v
1
rotation of the vertex
v
10
:
v
6
v
3
v
2
v
6
rotation of the vertex
v
11
:
v
4
v
1
v
5
v
4
rotation of the vertex
v
12
:
v
4
v
6
v
4
rotation of the vertex
v
13
:
v
3
v
6
v
4
v
3
Table 3.3. Planar configuration 3.
|
|
The set of graph cycles in the form of edges:
|
The set of graph cycles in the form of vertices:
|
The tuple of isometric cycles vertices:
|
|
๑
8
|
{e
5
,e
6
,e
12
,e
13
}
|
{v
9
,v
4
,v
8
,v
2
}
|
<
v
9
,v
4
,v
8
,v
2
>
|
|
๑
13
|
{e
8
,e
10
,e
13
,e
14
}
|
{v
8
,v
4
,v
13
,v
3
}
|
<
v
8
,v
4
,v
13
,v
3
>
|
|
๑
17
|
{e
12
,e
15
,e
18
,e
19
}
|
{v
9
,v
5
,v
12
,v
4
}
|
<
v
9
,v
5
,v
12
,v
4
>
|
|
๑
18
|
{e
14
,e
15
,e
20
,e
22
}
|
{v
13
,v
6
,v
12
,v
4
}
|
<
v
4
,v
12
,v
6
,v
13
>
|
|
๑
6
|
{e
4
,e
6
,e
8
,e
9
}
|
{v
7
,v
3
,v
8
,v
2
}
|
<
v
2
,v
8
,v
3
,v
7
>
|
|
๑
15
|
{e
10
,e
11
,e
20
,e
21
}
|
{v
13
,v
6
,v
10
,v
3
}
|
<
v
13
,v
6
,v
10
,v
3
>
|
|
๑
5
|
{e
2
,e
3
,e
17
,e
18
}
|
{v
9
,v
5
,v
11
,v
1
}
|
<
v
1
,v
11
,v
5
,v
9
>
|
|
c
1
|
{e
1
,e
2
,e
4
,e
5
}
|
{v
7
,v
2
,v
9
,v
1
}
|
<
v
1
,v
9
,v
2
,v
7
>
|
|
rim
|
{e
19
,e
22
,e
9
,e
11
,e
21
,e
3
,e
17
,e
1
}
|
{v
12
,v
6
,v
10
,v
3
,v
7
,v
1
,v
11
,v
5
}
|
<
v
5
,v
11
,v
1
,v
7
,v
3
,v
10
,v
6
,v
12
>
|
Fig. 5.
Planar configuration 3.
During planarization the edges
ๅ
7
and
ๅ
16
were removed.
Vertices rotation of the plane subgraph:
rotation of the vertex
v
1
:
v
7
v
9
v
11
v
7
rotation of the vertex
v
2
:
v
8
v
7
v
9
v
8
rotation of the vertex
v
3
:
v
8
v
13
v
10
v
7
v
8
rotation of the vertex
v
4
:
v
9
v
12
v
13
v
8
v
9
rotation of the vertex
v
5
:
v
9
v
11
v
12
v
9
rotation of the vertex
v
6
:
v
10
v
13
v
12
v
10
rotation of the vertex
v
7
:
v
2
v
3
v
1
v
2
rotation of the vertex
v
8
:
v
4
v
3
v
2
v
4
rotation of the vertex
v
9
:
v
2
v
1
v
5
v
4
v
2
rotation of the vertex
v
10
:
v
3
v
6
v
3
rotation of the vertex
v
11
:
v
5
v
1
v
5
rotation of the vertex
v
12
:
v
5
v
6
v
4
v
5
rotation of the vertex
v
13
:
v
4
v
6
v
3
v
4
It should be mentioned that vertex notation of cycle
tuples allows to write down cycles in vector form:
< v
9
,v
4
,v
8
,v
2
>
= (v
9
,v
4
) + (v
4
,v
8
) + (v
8
,v
2
)
+ (v
2
,v
9
);
< v
8
,v
4
,v
13
,v
3
>
= (v
8
,v
4
) + (v
4
,v
13
) + (v
13
,v
3
)
+ (
v
3
,
v
8
);
< v
9
,v
5
,v
12
,v
4
>
= (v
9
,v
5
) + (v
5
,v
12
) + (v
12
,v
4
)
+ (
v
4
,
v
9
);
< v
4
,v
12
,v
6
,v
13
>
= (v
4
,v
12
) + (v
12
,v
6
) + (v
6
,v
13
)
+ (
v
13
,
v
4
);
< v
2
,v
8
,v
3
,v
7
>
= (v
2
,v
8
) + (v
8
,v
3
) + (v
3
,v
7
)
+ (
v
7
,
v
2
);
< v
13
,v
6
,v
10
,v
3
>
= (v
13
,v
6
) + (v
6
,v
10
) + (v
10
,v
3
)
+ (
v
3
,
v
13
);
< v
1
,v
11
,v
5
,v
9
>
= (v
1
,v
11
) + (v
11
,v
5
) + (v
5
,v
9
)
+ (
v
9
,
v
1
);
< v
1
,v
9
,v
2
,v
7
>
= (v
1
,v
9
) + (v
9
,v
2
)
+ (v
2
,v
7
) + (
v
7
,
v
1
)
;
< v
5
,v
11
,v
1
,v
7
,v
3
,v
10
,v
6
,v
12
>=
(v
5
,v
11
) + (v
11
,v
1
) + (v
1
,v
7
)
+ (
v
7
,
v
3
) + (v
3
,v
10
)
+ (v
10
,v
6
) +
+ (v
6
,v
12
) + (
v
12
,
v
5
).
The sum of all vector transcriptions
for a planar configuration is an empty set, since
.
It should be noted that the subset of cycles
characterized by a zero value of the PontryaginKuratowski functional (or the
MacLane functional) cannot be a planar configuration, since it represents a subgraph
with an articulation point (r.t. Fig. 6 for illustration).
|
๑
13
|
{e
8
,e
10
,e
13
,e
14
}
|
{v
8
,v
4
,v
13
,v
3
}
|
|
๑
17
|
{e
12
,e
15
,e
18
,e
19
}
|
{v
9
,v
5
,v
12
,v
4
}
|
|
๑
18
|
{e
14
,e
15
,e
20
,e
22
}
|
{v
13
,v
6
,v
12
,v
4
}
|
|
๑
15
|
{e
10
,e
11
,e
20
,e
21
}
|
{v
13
,v
6
,v
10
,v
3
}
|
|
๑
16
|
{e
12
,e
16
,e
17
,e
18
}
|
{v
9
,v
5
,v
11
,v
4
}
|
|
๑
1
|
{e
1
,e
2
,e
4
,e
5
}
|
{v
7
,v
2
,v
9
,v
1
}
|
Fig. 6. Subgraph with an articulation point.
Now
let us consider the next step in constructing the topological drawing of a planar
subgraph. The theoretical rationale for this method is described in details in
[10-11].
We
consider this stage using the example of the following graph defined by the
incidentor. In this graph, we select one of the planar configurations, e.g.,
the following (Fig. 7).
Fig.7. Topological drawing of a planar
configuration.
Consider the rim of this planar
configuration as a closed sequence of oriented edges. We call such a
construction the coordinate-base system (CBS) [10,11]. Lets draw the edges
removed during the planarization process, which have two endpoint vertices
compatible with the vertices of the rim (see Fig. 7).
We write CBS in the form of a closed tuple
consisting of oriented edges
44
,e
70
,e
71
,e
39
,e
38
,e
32
,e
33
,e
40
,e
41
,e
58
,e
56
,e
53
,e
55
,e
72
,e
51
,e
52
,e
67
,e
14
,e
13
,e
6
,e
7
,e
18
,e
17
,e
25
,e
24
,e
46
,e
49
,e
47
,
e
68
,e
60
,e
20
,e
23
,e
35
,e
36
,e
28
,e
30
,e
43
>.
An undirected edge can be represented as two oppositely oriented directed edges
(arcs or arrows). Then for each arc there is a projection (in the set-theoretic
sense) onto the coordinate-base system. Exempli gratia (Fig. 8):
Fig. 8. Coordinate-base
system and drawn edges.
From two projections of the edge we
select one projection, which has the minimum length. In accordance with the
laws of the vector algebra of intersections, we assume that
the edges
intersect if their projections intersect
(in terms of the set-theory).
The
edges do not intersect if the result of the intersection of their projections
is an empty set or one projection is completely included into another
.
Consider the intersections of the edge e
9
.
From consideration follows that the edge e
9
intersects with all
edges except the edge e
50
.
To determine the removal of edges, it is necessary
to consider all cases of pairwise intersection of edges. After that, we can
sequentially remove edges that maximally intersect with others. At the end of
the process, the set of disjoint edges are isolated. For our example case, the disjoint
edges are shown in Fig. 9.
As a result, we obtain new simple cycles that can be
added to existing ones.
๑
15
=
{
e
37
,
e
43
,
e
41
,
e
70
,
e
71
,
e
39
};
๑
16
=
{
e
37
,
e
38
,
e
32
,
e
33
,
e
40
,
e
34
,
e
36
,
e
28
,
e
30
};
๑
17
=
{
e
34
,
e
41
,
e
61
,
e
20
,
e
23
,
e
35
};
๑
18
=
{
e
54
,
e
55
,
e
72
,
e
51
,
e
52
,
e
67
,
e
11
,
e
25
,
e
24
,
e
46
};
๑
19
=
{
e
11
,
e
17
,
e
18
,
e
6
,
e
7
,
e
15
};
c
0
= {
e
61
,
e
58
,
e
56
,
e
53
,
e
54
,
e
49
,
e
47
,
e
68
,
e
60
}.
Fig. 9.
Disjoint
connections
.
The totality of simple and isometric cycles forms the
topological drawing of the planar subgraph (Fig. 10).
Fig. 10. Topological drawing of the
planar subgraph.
In this paper, we consider the issues of applying the
diakoptic approach for construction of a topological drawing of the planar part
of a non-planar graph. It is demonstated that the solution to the problem of
distinguishing the planar part for the nonseparable subgraph of a non-planar
graph consists of two stages.
The first stage in constructing a topological
drawing is based on the matroid properties of the set of graph isometric
cycles. A method is proposed for isolating a topological drawing of the planar
part of a non-planar graph using structural number algebra methods. The initial
information for solving the problem on the first stage is the set of graph
isometric cycles, which allows us to reduce the solution to discrete
optimization methods.
The second stage of joining cycles is based on the
methods of vector algebra of intersections. The basis of this method is the
construction of a coordinate-base system, which is based on the rim of the isolated
planar part of the graph obtained on the first stage of the proposed solution.
1.
M.
Gary
, D. Johnson.
Computing machines and
hard-to-solve problems.
M.: Mir, 1982. 416 p.
2.
G.
Cron
.
Investigation of complex
systems in parts (diakoptics). Trans. with English. Moscow: Nauka, 1972.
544 p.
3.
G.
Ringel
.
Map Color Theorem. Repr.
of the orig. 1st ed. (1974), Springer, 2011. 212 p.
4.
T.
Kavitha
, C. Liebchen, K. Mehlhorn,
D. Michail, et al.
Cycle bases in graphs characterization, algorithms,
complexity, and applications // Comput. Sci. Rev. 2009. No.3. P.199243.
5.
M.
N. S.
Swamy
, K. Thulasiraman.
Graphs, networks, and
algorithms. J. Wiley & Sons, 1981.
6.
S.
Bellert
.
Analysis and synthesis of
electrical circuits by the method of structural numbers / S. Bellert, G.
Wozniacki. Moscow: Mir, 1972. 332 p.
7.
S.
MacLane
.
A combinatorial condition
for planar graphs // Fund. Math., 28. 1937. P. 2232.
8.
S.
V.
Kurapov
, A. V. Tolok.
The topological drawing of
a graph: Construction methods // Autom. Remote Control. 2013. Vol. 74, Issue 9.
P. 14941509.
9.
Kurapov
S. V, Davidovsky M. V.
Construction of a general
drawing of connections in planar structures // Components and technologies.
2016. No. 3. P. 7277.
10.
Rappoport
L. I., Morogovskiy B. N.,
Polivtsev S. A.
Vector algebra and projection of connection topology. In: Problems of
Automation of Design of Integrated Circuits. Kiev: IR of the USSR . 1976. P. 107124.
11.
Rappoport
L. I., Morogovskiy B. N.,
Polivtsev S. A.
Vector algebra of intersections // In: Multiprocessor computing
structures. Taganrog. 1982. Vyp. 2 (11). P. 5356.
