# Accession Number:

## AD0678431

# Title:

## ARRANGEMENT OF A GRAPH IN A PLANE (RASPOLOZHENIE GRAFA NA PLOSKOSTI),

# Descriptive Note:

# Corporate Author:

## FOREIGN TECHNOLOGY DIV WRIGHT-PATTERSON AFB OHIO

# Personal Author(s):

# Report Date:

## 1967-11-02

# Pagination or Media Count:

## 11.0

# Abstract:

The following two problems arise in the automatic designing of computers 1 Find an effective algorithm applicable to any graph G and determining whether or not the graph is planar 2 Find an effective algorithm applicable to any planar graph G and determining the cyclic orders induced by a certain planar realization of the graph G. It is proven that, in solving the above problems, it is sufficient to find the graphs which possess these properties a the graph has no coupling point b the degree of each node is not less than 3. Two lemmas are proven 1 if the graph G is planar, then for any of its cycles micro, the graph R micro will be bichromatic 2 if the graph R micro, a planar realization exists which induces this hue. On the above basis, a method of constructing a system of cycles with their bichromatic hues is described.

# Descriptors:

# Subject Categories:

- Theoretical Mathematics