David Eppstein - Publications

Journal of Graph Theory

• Connectivity, graph minors, and subgraph multiplicity.
  D. Eppstein.
  Tech. Rep. 92-06, ICS, UCI, 1992.
  J. Graph Th. 17:409-416, 1993.

  It was known that planar graphs have O(n) subgraphs isomorphic to K3 or K4. This paper characterizes the subgraphs for which such a linear bound holds: they are exactly the 3-connected planar graphs. Please note that the Tech. Rep. version had a bug (in a supposed generalization of the result to nonplanar graph families) which was corrected in the journal version.

  (BibTeX -- Citations -- CiteSeer -- ACM DL)

Journals -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine

Semi-automatically filtered from a common source file.