Quasiplanar and Pseudoplanar Graphs.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1978
- Accession Number
- ADA061523
Entities
People
- Ranel E. Erickson
Organizations
- Stanford University