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.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE