**Fast optimal parallel algorithms for maximal matching in sparse graphs**.

H. Asuri, M. Dillencourt, D. Eppstein, G. Lueker, and M. Molodowitch.

Tech. Rep. 92-01, ICS, UCI, 1992.We later discovered that the same results were published in a SPAA paper by Greg Shannon.

(BibTeX)

**Geometric thickness of complete graphs**.

M. Dillencourt, D. Eppstein, and D. S. Hirschberg.

*6th Int. Symp. Graph Drawing,*Montreal, August 1998.

Springer,*Lecture Notes in Comp. Sci.*1547, 1998, pp. 102–110.

arXiv:math.CO/9910185.

*J. Graph Algorithms and Applications*4 (3): 5–17, 2000 (special issue for GD98).We define a notion of geometric thickness, intermediate between the previously studied concepts of graph thickness and book thickness: a graph has geometric thickness T if its vertices can be embedded in the plane, and its edges partitioned into T subsets, so that each subset forms a planar straight line graph. We then give upper and lower bounds on the geometric thickness of complete graphs.

(Springer abstract – BibTeX – CiteSeer – Citations – ACM DL – GDEA)

**Uninscribable four-regular polyhedron**.

M. Dillencourt and D. Eppstein.

*Electronic Geometry Models*2003.08.001.We find an example of a three-dimensional polyhedron, with four edges per vertex, that can not be placed in convex position with all vertices on the surface of a sphere.

**Choosing colors for geometric graphs via color space embeddings.**

M. Dillencourt, D. Eppstein, and M. T. Goodrich.

arXiv:cs.CG/0609033.

14th Int. Symp. Graph Drawing, Karlsruhe, Germany, 2006.

Springer,*Lecture Notes in Comp. Sci.*4372, 2007, pp. 294–305.We show how to choose colors for the vertices of a graph drawing in such a way that all colors are easily distinguishable, but such that adjacent vertices have especially dissimilar colors, by considering the problem as one of embedding the graph into a three-dimensional color space.

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

Semi-automatically filtered from a common source file.