Quasiplanar and Pseudoplanar Graphs.
STANFORD UNIV CALIF DEPT OF OPERATIONS RESEARCH
Pagination or Media Count:
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.
- Numerical Mathematics