# Accession Number:

## ADA061523

# Title:

## Quasiplanar and Pseudoplanar Graphs.

# Descriptive Note:

## Technical rept.,

# Corporate Author:

## STANFORD UNIV CALIF DEPT OF OPERATIONS RESEARCH

# Personal Author(s):

# Report Date:

## 1978-05-01

# Pagination or Media Count:

## 34.0

# Abstract:

Two new generalizations of planar graphs, called quasiplanar and pseudoplanar graphs, are introduced and discussed. A graph is called quasiplanar if for each node t, the set of nodes incident to t can be labeled 1, ... , m so that for each 1 or h i j k or m, each pair of paths not containing t and having respective endnodes h,j and i,k share a common node. A directed graph is called pseudoplanar if for each pair of nodes s,t, the set of nodes adjacent to t can be labeled 1, ... , m so that for each maximal arborescence not containing t and having root s and each endnode adjacent to t, the endnode descendants of each node in the arborescence are either j, ... , k or k, ... ,m, 1, ... , j for some 1 or j or k or m. Planar graphs are quasiplanar and they in turn are pseudoplanar. Conversely, a pseudoplanar graph that contains with each arc its reverse arc is quasiplanar. And a quasiplanar graph that excludes subgraphs that are refinements of the complete bipartite graph K sub 33 with three nodes in both sets is planar.

# Descriptors:

# Subject Categories:

- Numerical Mathematics