David Eppstein - Publications

Ramsey 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)

• New algorithms for minimum area k-gons.
  D. Eppstein.
  Tech. Rep. 91-59, ICS, UCI, 1991.
  3rd ACM-SIAM Symp. Discrete Algorithms, Orlando, 1992, pp. 83-86.

  Shows that the minimum area polygon containing k of n points must be near a line determined by two points, and uses this observation to find the polygon quickly. Merged with "Iterated nearest neighbors and finding minimal polytopes" in the journal version.

  (BibTeX -- Citations)

• Separating geometric thickness from book thickness.
  D. Eppstein.
  arxiv:math.CO/0109195.

  We show that geometric thickness and book thickness are not asymptotically equivalent: for every t, there exists a graph with geometric thickness two and book thickness > t.

  (BibTeX -- Citations -- GDEA)

• Separating thickness from geometric thickness.
  D. Eppstein.
  arxiv:math.CO/0204252.
  10th Int. Symp. Graph Drawing, Irvine, 2002.
  Lecture Notes in Comp. Sci. 2528, 2002, pp. 150-161, © Springer-Verlag.
  In Towards a Theory of Geometric Graphs, AMS, 2004, Contemporary Math 342, J. Pach, ed., pp. 75-86.

  We show that thickness and geometric thickness are not asymptotically equivalent: for every t, there exists a graph with thickness three and geometric thickness > t. The proof uses Ramsey-theoretic arguments similar to those in "Separating book thickness from thickness".

  (BibTeX -- GD'02 talk slides -- Citations -- ACM DL)

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

Semi-automatically filtered from a common source file.