User: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.

Not about me

Scam warning

If you are visiting this page because someone claiming to be me contacted you asking for any payment for any action relating to Wikipedia, it is not me and you are being scammed. If they are threatening to delete or take other adverse action against some article, they can't actually do that and you should not under any circumstances pay them any money or further engage with them.

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.

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.

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 the circle packing theorem has been used to construct flattened maps of the human brain? (26.02)

... that a photograph of an airplane propeller taken by a camera with a rolling shutter (pictured) may distort the propeller into curves resembling the quadratrix of Hippias? (26.02)
... that Euclid's Elements has been estimated to be second only to the Bible in its number of published editions? (25.10)
... that Pythagorean addition, available in many programming libraries as hypot, can compute distances, polar coordinates, and the relativistic energy of moving objects? (25.09)
... that boxing rings are square, despite their name? (25.08)
... that Leonardo da Vinci invented a device to solve Alhazen's problem, instead of finding a mathematical solution? (25.07)
... that Ewa Ligocka cooked another mathematician's goose? (24.11)

(Older entries)

Good articles

17-animal inheritance puzzle – Mathematical puzzle
2-satisfiability – Logic problem, AND of pairwise ORs
Alexandrov's theorem on polyhedra – Polyhedra are determined by surface distance
Alhazen's problem – On reflection in a spherical mirror
antiparallelogram – Polygon with four crossed edges of two lengths
arc diagram – Graph drawing with vertices on a line
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
circle packing theorem – On tangency patterns of circles
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 same width in all directions
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
Euclid's Elements – Mathematical treatise by Euclid
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 (1921–2008)
Ronald Graham – American mathematician (1935–2020)
grid bracing – Mathematical problem of making a structure rigid
Halin graph – Mathematical tree with cycle through leaves
handshaking lemma – Every graph has evenly many odd vertices
harmonic series (mathematics) – Divergent sum of 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
intersection number (graph theory) – Fewest cliques covering a graph's edges
isosceles triangle – Triangle with at least two sides congruent
Vojtěch Jarník – Czech mathematician (1897–1970)
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)
Lambek–Moser theorem – On integer partitions from monotonic functions
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
matroid parity problem – Largest independent set of paired elements
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 orderings allowing ties
paper fortune teller – Origami toy used for children's games
parallelohedron – Polyhedron that tiles space by translation
Perles configuration – Irrational system of points and lines
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 addition – Hypotenuse of right triangle from its sides
Pythagorean tiling – Tiling by squares of two sizes
quadratrix of Hippias – Curve where spinning and moving lines cross
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 – Shape with four equal sides and angles
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
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
Yao's principle – Equivalence of average-case and expected complexity
YBC 7289 – Babylonian mathematical clay tablet
Znám's problem – On divisibility among sets of integers