**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 K_{3}or K_{4}. That is, K_{3}and K_{4}have linear subgraph multiplicity. This paper shows that the graphs with linear subgraph multiplicity in the planar graphs are exactly the 3-connected planar graphs. Also, the graphs with linear subgraph multiplicity in the outerplanar graphs are exactly the 2-connected outerplanar graphs.More generally, let F be a minor-closed family, and let x be the smallest number such that some complete bipartite graph K

_{x,y}is a forbidden minor for F. Then the x-connected graphs have linear subgraph multiplicity for F, and there exists an (x − 1)-connected graph (namely K_{x − 1,x − 1}) that does not have linear subgraph multiplicity. When x ≤ 3 or when x = 4 and the minimal forbidden minors for F are triangle-free, then the graphs with linear subgraph multiplicity for F are exactly the x-connected graphs.Please refer only to the journal version, and not the earlier technical report: the technical report had a bug that was repaired in the journal version.

**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.**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*.**Separating thickness from geometric thickness**.

D. Eppstein.

arXiv:math.CO/0204252.

10th Int. Symp. Graph Drawing, Irvine, 2002.

Springer,*Lecture Notes in Comp. Sci.*2528, 2002, pp. 150–161.

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.