Premium
Generalizations of planar graphs
Author(s) -
Erickson Ranel E.
Publication year - 1982
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230120205
Subject(s) - combinatorics , bipartite graph , mathematics , pathwidth , 1 planar graph , planar graph , indifference graph , chordal graph , discrete mathematics , outerplanar graph , graph , line graph
Two new generalizations of planar graphs, called quasiplanar and pseudoplanar graphs, are introduced and discussed. It is shown that planar graphs are quasiplanar and these in turn are pseudoplanar. Conversely, a pseudoplanar graph that contains with each arc its reverse arc is quasiplanar. A Kuratowski‐type characterization of quasiplanar graphs is given; in it the excluded subgraphs differ from Kuratowski's only by the addition of an edge in the bipartite graph.