David Eppstein

Wikipedia editor (n.) Someone who will not leave a burning building until you show them the newspaper article documenting how many people were killed by the fire.

About me

I'm a computer science professor at UC Irvine, in Orange County, California. See my home page, Mastodon account, blog, or even my Wikipedia article for more about me.

Much of my Wikipedia editing is on mathematics articles, but I've also edited articles on computer science, academic biography, the arts, and California geography, among many other topics. I've also contributed many diagrams and photographs to Wikipedia and Wikimedia Commons.

As an employee of a public university I believe that public outreach is part of my job description, and in that sense that my edits here to subjects within my professional expertise are paid edits. However, the topics and content of my editing here are wide-ranging and entirely self-directed. I neither participate in, nor condone, paid edits for specific articles or specific content.

This is a Wikipedia user page.
This is not an encyclopedia article or the talk page for an encyclopedia article. If you find this page on any site other than Wikipedia, you are viewing a mirror site. Be aware that the page may be outdated and that the user whom this page is about may have no personal affiliation with any site other than Wikipedia. The original page is located at https://en.wikipedia.org/wiki/User:David_Eppstein.

Wikibooks

Click on the titles, not on the cover images!


Graph Algorithms


Graph Drawing


Fundamental Data Structures


Matroid Theory


Perfect Graphs

Did you know?

... that Jenya Kazbekova, a competition climber on the Ukraine's 2024 Olympic team, is the daughter and granddaughter of competition climbing medalists? (24.08)
... that electrical engineering professor Mariesa Crow raises alpacas? (24.08)
... that Piper Kelly secured her position as a competitor in speed climbing at the 2024 Olympics by reaching the final race at the 2023 Pan American Games, before winning the race? (24.08)
... that although the icosian game was advertised as a "highly amusing game for the drawing room", it was too easy to play and not a commercial success? (24.05)
... that the discovery of Descartes' theorem in geometry came from a too-difficult mathematics problem posed to a princess? (24.04)
.. that Latvian-Soviet artist Karlis Johansons exhibited a skeletal tensegrity form of the Schönhardt polyhedron seven years before Erich Schönhardt's 1928 paper on its mathematics? (24.02)

(Older entries)

Good articles

17-animal inheritance puzzle – Mathematical puzzle
Alexandrov's uniqueness theorem – Polyhedra are determined by surface distance
antiparallelogram – Polygon with four crossed edges of two lengths
arrangement of lines – Subdivision of the plane by lines
Mark Barr – English-American inventor and polymath (1871–1950)
Beckman–Quarles theorem – Unit-distance-preserving maps are isometries
binary logarithm – Exponent of a power of two
binary tiling – Tiling of the hyperbolic plane
BIT predicate – Test of a specified bit in a binary number
book embedding – Graph layout on multiple half-planes
Borromean rings – Three linked but pairwise separated rings
bucket queue – Data structure for integer priorities
Cairo pentagonal tiling – Tiling of the plane by pentagons
Cantor's isomorphism theorem – Uniqueness of countable dense linear orders
Cartesian tree – Binary tree derived from a sequence of numbers
clique problem – Task of computing complete subgraphs
component (graph theory) – Maximal subgraph whose vertices can reach each other
constructible number – Number constructible via compass and straightedge
convex curve – Type of plane curve
convex hull – Smallest convex set containing a given set
cop-win graph – Type of graph related to pursuit–evasion
curve of constant width – Shape with width independent of orientation
curve-shortening flow – Motion of a curve based on its curvature
De Bruijn–Erdős theorem (graph theory) – On coloring infinite graphs
De quinque corporibus regularibus – 15th century book on polyhedra
Descartes' theorem – Equation for radii of tangent circles
Dehn invariant – Value determined from a polyhedron
directed acyclic graph – Directed graph with no directed cycles
double bubble theorem – On smallest surface enclosing two volumes
Doyle spiral – Circle packing arranged in spirals
dual graph – Graph representing faces of another graph
dyadic rational – Fraction with denominator a power of two
Earth–Moon problem – Unsolved problem on graph coloring
Erdős–Anning theorem – On sets of points with integer distances
Erdős–Ko–Rado theorem – Upper bound on intersecting set families
Erdős–Straus conjecture – On unit fractions adding to 4/n
Euclid–Euler theorem – Characterization of even perfect numbers
Euclidean distance – Length of a line segment
Euclidean minimum spanning tree – Shortest network connecting points
factorial – Product of numbers from 1 to n
farthest-first traversal – Sequence of points far from previous points
feedback arc set – Edges that hit all cycles in a graph
Fermat's right triangle theorem – Rational right triangles cannot have square area
Fibonacci nim – Game of taking coins from a pile
free abelian group – Algebra of formal sums
Gale–Shapley algorithm – Procedure for finding a stable matching
Garden of Eden (cellular automaton) – Pattern that has no predecessors
Andrew M. Gleason – American mathematician and educator
Ronald Graham – American mathematician (1935–2020)
Halin graph – Mathematical tree with cycle through leaves
handshaking lemma – Every graph has evenly many odd vertices
harmonic series (mathematics) – Divergent sum of all positive unit fractions
Heilbronn triangle problem – On point sets with no small-area triangles
C. Doris Hellman – American historian of science (1910–1973)
Herschel graph – Bipartite non-Hamiltonian polyhedral graph
hyperbolic spiral – Spiral asymptotic to a line
icosian game – Game of finding cycles on a dodecahedron
ideal polyhedron – Shape in hyperbolic geometry
infinity symbol – Mathematical symbol representing infinity
integer sorting – Computational task of sorting whole numbers
isosceles triangle – Triangle with at least two sides congruent
Vojtěch Jarník – Czech mathematician
Jessen's icosahedron – Right-angled non-convex polyhedron
Kawasaki's theorem – Description of flat one-vertex origami
Keller's conjecture – Geometry problem on tiling by hypercubes
Kepler triangle – Right triangle related to the golden ratio
kite (geometry) – Quadrilateral symmetric across a diagonal
Harry R. Lewis – American computer scientist (born 1947)
Laves graph – Periodic spatial graph
linear probing – Computer programming method for hashing
logic of graphs – Logical formulation of graph properties
Malfatti circles – Three tangent circles in a triangle
midsphere – Sphere tangent to every edge of a polyhedron
Möbius strip – Non-orientable surface with one edge
mutilated chessboard problem – On domino tiling after removing two corners
nearest-neighbor chain algorithm – Stack-based method for clustering
no-three-in-line problem – Geometry problem on grid points
opaque set – Shape that blocks all lines of sight
ordered Bell number – Number of weak orderings
paper fortune teller – Origami toy used for various children's games
perfect graph – Graph with tight clique-coloring relation
Pick's theorem – Formula for area of a grid polygon
polygonalization – Polygon through a set of points
prime number – Number divisible only by 1 or itself
Prince Rupert's cube – Cube that fits through hole in smaller cube
pseudoforest – Graph with at most one cycle per component
Pythagorean tiling – Tiling by squares of two sizes
quadrisecant – Line through four points of a curve
Rado graph – Infinite graph containing all countable graphs
random binary tree – Binary tree selected at random
regular number – Numbers that evenly divide powers of 60
Reuleaux triangle – Curved triangle with constant width
reversible cellular automaton – Cellular automaton that can be run backwards
rook's graph – Graph of chess rook moves
Klaus Roth – British mathematician (1925–2015)
Rule 90 – Elementary cellular automaton
Rule 184 – Elementary cellular automaton
Schönhardt polyhedron – Non-convex polyhedron with no triangulation
Schwarz lantern – Near-cylindrical polyhedron with large area
selection algorithm – Method for finding kth smallest value
Shapley–Folkman lemma – Sums of sets of vectors are nearly convex
simple polygon – Shape bounded by non-intersecting line segments
small set expansion hypothesis – Computational hardness assumption
snark (graph theory) – 3-regular graph with no 3-edge-coloring
square-difference-free set – Numbers whose differences are not squares
square pyramidal number – Number of stacked spheres in a pyramid
squaring the circle – Problem of constructing equal-area shapes
Stars (M. C. Escher) – Wood engraving print by M. C. Escher
Steinitz's theorem – Graph-theoretic description of polyhedra
Carl Størmer – Norwegian geophysicist and mathematician
Sylvester–Gallai theorem – Existence of a line through two points
Sylvester's sequence – Doubly exponential integer sequence
telephone number (mathematics) – Number of ways to pair up n objects
Theil–Sen estimator – Statistical method for fitting a line
three-gap theorem – On distances between points on a circle
three utilities problem – Mathematical puzzle of avoiding crossings
triaugmented triangular prism – Convex polyhedron with 14 triangle faces
Turán's brick factory problem – On minimizing crossings in bicliques
2-satisfiability – Logic problem, AND of pairwise ORs
unit distance graph – Geometric graph with unit edge lengths
unit fraction – One over a whole number
universal vertex – Vertex adjacent to all others in a graph
Viète's formula – Infinite product converging to 2/π
well-covered graph – Graph with equal-size maximal independent sets
widest path problem‎ – Path-finding using high-weight graph edges
witch of Agnesi – Cubic plane curve
$X + Y$ sorting – Problem of sorting pairs of numbers by their sum
YBC 7289 – Babylonian mathematical clay tablet
Znám's problem – On divisibility among sets of integers