Кібернетика та комп'ютерні технології (Jun 2025)
On the Synthesis of Planar Graphs with Given Properties
Abstract
The problem of studying the structural properties of planar subgraphs G\v, where v is an arbitrary vertex of a graph G of undirected genus, is considered, using cell chains that connect limit cycles with points of a given set M of the graph G\v. Through the sum of the minimum in length and a number of cell chains covering M, we determine the cell distance of a given subset of the set of points of graph G. The goal is to synthesize planar graphs of a certain subset of points with a fixed length of the cell distance from at least two graphs with subsets of points of a smaller cell distance by identification by simple chains or simple cycles. To the graphs thus obtained, minimal with respect to the operation of removing an arbitrary edge or point from M, we attach a simple star or quasi-star with a center – a planar graph by pairwise identification of hanging vertices with points of the set M to points of the graph G. The tangent problem was considered in [6]. In [7, 8], a similar problem of covering a set of vertices by no more than a given k – number of cycles-boundaries of 2-cells was considered, and the number of minimal planar graphs was calculated for k=3, for an arbitrary k we will have an algorithm for constructing minimal graphs with exponential time complexity. The concept of cell distance is given in [9, 10], where the lower bound of the oriented genus of the apex graph formed from planar graphs and a simple star glued to a given set of graph points was investigated. In a certain way, this problem is related to the Erdos conjecture [3] about the covering of obstruction graphs of a nonorientable surface of genus k, where k>0, by the smallest set of inclusions from the k+1-th graph homeomorphic to K5 or K3,3. In [5], the existence of a finite set of obstruction graphs for an nonorientable surface was proved. The article has an introduction and a main part. The main results – the structure of planar graphs with a given reachability number and a cell distance of a given set of points was investigated using the φ-transformation method; lists of planar graphs with a given set of points with cell distances 1 and 2 were given; the boundaries of an undirected genus of graphs represented as a φ-image of a simple star or quasi-star and a planar graph were established with pairwise identification of hanging vertices with points of the set of a planar graph of a given cell distance were established.
Keywords
