User:David Eppstein/Gallery
(Redirected from User:David Eppstein)
See me on Wikipedia.
Mathematical illustrations
[edit]I've placed most of the following mathematical illustrations in the public domain. If you see an illustration I've drawn for one of my other web sites, and want it to be uploaded to the commons for whatever reason, please ask by email: if I upload it myself, it can be more properly licensed, and it's likely that I still have the vectorized source instead of the rasterized version I use for web images.
Configurations and point-line incidences
[edit]-
Suboptimal no-3-in-line placement by the method of Erdős
-
Dual arrangement to a regular pentagon
-
Non-Desargues configuration
-
Complete quadrangle and dual complete quadrilateral
-
Desargues configuration as two mutually inscribed pentagons
-
Point sets with fewer than n/2 ordinary lines
Geometric graph theory
[edit]-
Grid bracing and its graph-theoretic analysis
-
Flexibility of an unbraced square grid in the grid bracing problem
-
Greedy geometric spanner with distance ratio 1.1
-
Greedy geometric spanner with distance ratio 2
-
Triangle-free penny graph
-
The smallest cubic matchstick graph
-
Integral Fáry embedding of the octahedron
-
Forbidden induced subgraphs of indifference graphs
-
Slope number of the Petersen graph
-
Slope number of bounded-degree planar graphs
-
Empty regions for the β-skeleton
-
String graph representation of a planar graph
-
Ageev's 5-chromatic circle graph
-
An intersection graph of rectangles, with boxicity two.
-
Hadwiger–Nelson problem: 7-coloring of the plane and 4-chromatic unit distance graph. From the junkyard.
-
A 3-colored triangulation for Fisk's proof of the art gallery theorem. From my WG09 slides.
Cayley graphs and symmetric graphs
[edit]-
The Johnson graph J(4,2)
-
drawn with three crossings
-
The smallest zero-symmetric graph with only two edge orbits
-
The graph of the 3-3 duoprism
-
Paley graph of order 9 and one of its triangles
-
7-vertex antihole graph
-
K5 subdivision of a crown graph illustrating the Kelmans–Seymour conjecture
-
Distinguishing coloring of a 6-key keyring (6-vertex cycle graph)
-
distinguishing coloring of a hypercube
-
1-planar 8-crossing Nauru graph
-
Hamiltonicity of the truncated octahedral graph
-
18-vertex zero-symmetric graph
-
The unique edge coloring of G(9,2)
-
12-vertex crown graph
-
Perfect matchings in a complete graph, or chord diagrams
-
K5 and K3,3 as minors of the Petersen graph
-
K2,2,2,2 as a 1-planar graph
-
Cycle and its complement
-
Matchings in a complete graph
-
Butterfly network as a multitree
-
Johnson graph J(5,2)
-
The Clebsch graph labeled as in a construction for Keller's conjecture
-
The path formed by the Steinhaus–Johnson–Trotter algorithm
-
K3,3 with each of its three color classes drawn as parallel line segments on distinct lines
-
Edge coloring of a complete graph
-
The Clebsch graph
-
Construction of the Clebsch graph from a hypercube
-
One-crossing drawing of K3,3
-
A generalized Petersen graph with only three Hamiltonian cycles
-
The Shrikhande graph in Lombardi style
-
The Folkman graph in Lombardi style
-
The octahedron as pancyclic graph
-
The odd graph O4
-
3-crossing drawing of the Heawood graph
-
The Petersen graph and its complement
-
The Nauru graph drawn as a unit distance graph
-
The intersection graph of the faces of a cube
-
Toroidal Nauru graph
-
Genus-4 Nauru graph
-
The Wagner graph
-
The Petersen graph as a Kneser graph
-
The Shrikhande graph embedded on a torus.
-
The Gray graph.
-
The Folkman graph.
-
The Möbius–Kantor graph as a unit distance graph.
-
The Möbius–Kantor graph embedded symmetrically on a torus.
-
The cube-connected cycles of order 3.
-
The Paley graph of order 9 as a perfect graph.
-
The Petersen graph as a Moore graph.
-
Two views of the Möbius ladder graph M16
-
The De Bruijn graph as a line graph
-
Three-dimensional binary De Bruijn graph
-
Paley graph, of order 13, as a circulant
Dessins d'enfants
[edit]-
Transforming a dessin d'enfant into gluing instructions for a Riemann surface
-
The dessins d'enfants for the Chebyshev polynomials
-
The dessin d'enfant for the sextic monomial p(x)=x6
-
Two conjugate dessins d'enfants
Miscellaneous graph theory and graph drawing
[edit]-
Graphs with a universal vertex
-
Optimal coloring of a split graph
-
15-vertex planted clique in 32-vertex random graph
-
18-vertex planted clique in 64-vertex random graph
-
A graph of cutwidth 2
-
K5 triangle packing and covering
-
The 2-core of a graph
-
The diamond graph and its line graph
-
Petersen minor in the flower snark
-
A bipartite graph and its line graph
-
Complementary perfect graphs
-
The Fritsch graph and its dual map
-
26-fullerene graph with distance labels
-
Unit distance graph with 16 vertices and 40 edges
-
Dominated vertex
-
Tree with 480 symmetries, example for Jordan–Pólya number
-
Feedback arc set NP-completeness
-
Feedback arc set
-
3-colorings of a square, up to symmetry
-
3-colorings of a path graph
-
Hamiltonian path in the Herschel graph
-
Medial graph of the Herschel graph
-
Example for Grötzsch's theorem
-
The densest possible planar locally linear graphs
-
Layers of a planar drawing of the graph of a rhombic dodecahedron
-
Illustration for the proof of Ore's theorem
-
Hamiltonian cycle in which nonadjacent pairs of vertices have degrees summing to at least n, for Ore's theorem
-
Lombardi drawing of the Golomb graph
-
The extension property of the Rado graph
-
Graphic matroid parity
-
Tangled Kempe chains in the Errera graph
-
Tangled Kempe chains in the Poussin graph
-
Clique-width construction
-
A Halin graph without any 8-cycles
-
Pagewidth
-
Book crossing number
-
An equilibrium stress
-
Scorpion graph
-
Bidirected graph features
-
A 2-degenerate graph and its 2-core
-
Crossing number and 1-planarity of Tietze's graph
-
Tietze's graph on a Möbius strip
-
Nonisomorphic planar duals
-
A line perfect graph
-
Partition of a line graph into cliques
-
A planar DAG that is not upward planar
-
Grid drawing of nested triangles graph
-
Euler tour of a tree
-
Unordered binary trees with four leaves
-
Vertex-face coloring
-
A bramble in a 3x3 grid graph
-
List coloring for K3,27
-
Moser spindle as a pseudotriangulation
-
A planar Lombardi drawing of the Frucht graph
-
A Hamiltonian cycle in the Dürer graph
-
A multigraph that has degree six, edge multiplicity three, and requires nine colors in any edge coloring
-
A 3-regular planar graph that requires four colors in any edge coloring
-
The Frucht graph in Lombardi drawing style
-
The Chvátal graph in Lombardi style
-
An apex graph
-
Robertson's irreducible apex graph
-
The Petersen family
-
The Herschel graph
-
Planar separator for a grid graph
-
Forbidden minors for branchwidth three
-
Domination in a product of stars, for Vizing's conjecture
-
Subdivision of K5
-
The Herschel graph
-
Forming a Schlegel diagram from shadows and light
-
The Rado graph
-
A cycle double cover of the Petersen graph
-
Finding matchings in claw-free graphs
-
An augmenting path in a claw-free graph
-
A forbidden subgraph for comparability graphs
-
Thomassen's girth-3 hypohamiltonian graph
-
Construction of a distance-hereditary graph
-
The median graph representing the set of solutions to a 2-satisfiability instance
-
A squaregraph
-
Converting a triangle-free graph into a median graph.
-
The Buneman graph, a median graph representing maximum-parsimony evolutionary relationships.
-
The retraction of a cube onto a median graph.
-
The median of three vertices in a median graph.
-
The median of three vertices in a tree.
-
A cograph described by a cotree.
-
A forbidden subgraph for the line graphs of hypergraphs
-
Forbidden minors for partial 3-trees.
-
A graph and its tree decomposition.
-
An interval graph.
-
Partition of the complete bipartite graph K4,4 into three forests, showing that it has arboricity three.
-
The butterfly and diamond, forbidden minors for pseudoforests.
-
A pseudoforest.
-
A 4x4 grid graph and one of its spanning trees.
-
Fáry's theorem, induction step of proof
-
An aperiodic graph.
-
A graph that is not aperiodic as all cycles are divisible by three.
-
The Turán graph T(13,4).
-
Thue number of the 5-cycle is four
-
Wheel graphs with 4 to 9 vertices.
-
Beineke's nine forbidden line graphs.
-
Partition of the torus into seven mutually adjacent regions, for Heawood conjecture.
-
The Grötzsch graph.
-
König's theorem proof
-
König's theorem example
-
Erdős–Gyárfás conjecture, Markström's 4- and 8-cycle-free graph
Miscellaneous geometry
[edit]-
Density in the binary tiling
-
Geometric structure of M. C. Escher's Regular Division of the Plane VI
-
Polygon with no exposed ears
-
Pythagorean dense rational distance set
-
Stereographic projection of an spherical octahedron and its associated circle packing
-
Illustration for a proof of the Erdős–Anning theorem
-
Grid points within a convex polygon
-
Polygonalizations of a 3x3 grid
-
Boscovich's cardioid
-
Intersections of a line with a convex curve
-
Decagon simplicial arrangement
-
Three circles associated with an antiparallelogram
-
Tangent circles to the extended sides of an antiparallelogram
-
Two circles tangent to the extended sides of a non-convex kite
-
The inscribed circle and ex-tangential circle of a kite
-
A kite and its dual isosceles trapezoid
-
Triaugmented triangular prism net
-
A fractal rosette of Penrose kites
-
Unflippable polygon
-
16 polygonalizations of a set of six points
-
Planar double bubbles
-
Crease pattern for Schwarz lantern
-
Empty regions for the Euclidean minimum spanning tree
-
Geometry of pentagons in the dual snub square tiling
-
Maximum in-radius isosceles triangle
-
Translucent Jessen icosahedron
-
Greek cross to rectangle dissection
-
Lifted frustum
-
Two orthogonal polyhedra
-
Fractal opaque set for a square
-
Opaque forests for a circle
-
7 disks can cover a single disk of twice the radius
-
Triangulating a grid polygon with primitive triangles
-
Tiling the plane with primitive triangles
-
Distance contours in a square grid
-
81 grid points in a radius-5 circle
-
Crossed lines method for curves of constant width
-
Comparison of Blichfeldt's theorem with Minkowski's theorem
-
Collinear form of Cairo pentagonal tiling
-
Equilateral form of Cairo pentagonal tiling
-
Reuleaux triangle and its middle hedgehog
-
Curve of constant width based on a semi-ellipse
-
Tresillo rhythm as a polygon
-
Convex curve through 13 grid points
-
Partition of a cyclic pentagon into isosceles triangles
-
4-hexagon net for an octahedron
-
Partitions of a square into similar rectangles
-
Ordinary lines
-
Ambiguity in network curve-shortening
-
Self-similar lens shape under curve-shortening
-
Curve-shortening of a convex curve
-
The grim reaper curve
-
Polyhedral Delta-Y transformations
-
Visual proof of Balinski's theorem
-
Non-convex pentagonal tiling
-
Non-convex pentagonal tiling
-
The Reuleaux triangle in a cluster of four soap bubbles
-
Euclid XIII.10
-
Heesch's anisohedral tiling
-
89th stage of toothpick sequence
-
Overlaid Pythagorean tilings
-
Coloring argument for De Bruijn's theorem
-
Non-harmonic packing for De Bruijn's theorem
-
Reuleaux kite
-
Circles meeting at the isodynamic point
-
Construction of the isodynamic point
-
Subdivisions of a pentagon
-
Pythagorean dissections
-
Similarity tiling by Koch snowflakes
-
Aperiodic section of the Pythagorean tiling
-
Tiling of the plane by shifted squares
-
Inner radius
-
Skew lines on nested hyperboloids
-
A cube dissected into orthoschemes.
-
A Davenport–Schinzel sequence from a lower envelope of line segments
-
The Fermat–Apollonius circle of an ellipse.
-
The trisected perimeter point of a 3-4-5 right triangle.
-
Four levels of the Z-curve
-
Z-curve via interleaved binary coordinates
-
The Brocard point of a triangle
-
Intersecting planes
-
Chao's characterization of tangential quadrilaterals
-
Convex layers and a halfspace. For an example in fractional cascading.
-
Happy Ending problem, eight points with no pentagon
-
The Szilassi polyhedron. From the junkyard.
-
The face lattice of a square pyramid.
-
The Nagel point of a triangle.
-
The Philo line and its application to doubling the cube.
-
Heesch's problem, Amman's dented hexagon. From the junkyard.
-
Happy Ending problem, quadrilaterals in five-point sets.
-
Erdős–Szekeres theorem, geometric interpretation as monotone path
Number theory and combinatorics
[edit]-
Gomory's theorem on domino tiling mutilated chessboards
-
A chessboard region with no domino tiling but equal colors
-
Lambek–Moser theorem for prime numbers
-
Dyadic approximation of
-
Numbers without unusually-accurate dyadic approximations
-
Relative error of approximations to the prime-counting function
-
Primes vs composites
-
Growth rate of the Moser–de Bruijn sequence
-
Addition of numbers in the Moser–de Bruijn sequence
-
A cap set
-
Bijection between binary trees and stack-sortable permutations
-
Lower bound construction for the Erdős–Ko–Rado theorem
-
Two right triangles, with one hypotenuse the square of the other
-
Trees counted by the Wedderburn–Etherington numbers
-
Dickson's lemma applied to the hyperbola xy ≥ 9
-
Trees counted by the ordered Bell numbers
-
Representation of octahedral numbers as centered square pyramids
-
15=4+5+6 is a polite number
-
Graphical demonstration of a solution to Znám's problem.
-
Graphical demonstration that 1 = 1/2 + 1/3 + 1/7 + 1/43 + ...; see Sylvester's sequence.
-
Rational approximations to the octagon from Pell numbers.
-
Integer right triangles with nearly-equal legs from Pell numbers.
-
Divisibility of regular numbers.
Order theory
[edit]-
2-dimensional modular lattice
-
A fence
-
The extreme case for the 1/3–2/3 conjecture
-
Example for Birkhoff's representation theorem.
-
The Hasse diagram of a distributive lattice.
-
Dilworth's theorem, transformation from chain decomposition to bipartite matching.
-
The 13 possible strict weak orderings on a set of three elements.
-
A partial order of dimension 4 and its realizer.
-
The lattice of subgroups of Dih4.
-
Three views of an antimatroid.
Cellular automata
[edit]-
Anneal
-
1d reversible CA defined from a rectangular band
-
Critters transition rule
-
Rule 90 gate array
-
Trees in Rule 90
-
Critters
-
Day & Night, Bell's p256 butterfly gun
-
One-dimensional cyclic cellular automaton.
-
Two-dimensional cyclic cellular automaton.
-
The space rake.
-
Rule 184 as a model of traffic flow.
-
Rule 184 as a model of deposition.
-
Rule 184 as a model of ballistic annihilation.
Algorithms and data structures
[edit]-
Binary tree from random insertions
-
Uniformly random binary tree
-
Extended binary tree
-
Finding the median of 5 values in 6 comparisons
-
Another SPQR tree
-
Reduction from 3SAT to 3-coloring
-
An SPQR tree.
-
Consecutive pairs that bracket x in a sequence, for the Cartesian tree article
-
Using a Cartesian tree for range searching
-
Floyd's "tortoise and hare" cycle detection algorithm.
Topology
[edit]-
Pentagonal Möbius strip
-
5-vertex polyhedral Möbius strip
-
6-vertex polyhedral strip with triangular boundary
-
Level sets of a cross-cap
-
Symmetric Whitehead link
-
Six-component "rubberband" Brunnian link
-
Algebraic link diagram for the Borromean rings
-
Trefoil with bridge number 2
-
A train track on a triple torus.
-
A switch in a train track.
Miscellaneous
[edit]-
Monotone piecewise linear function
-
Combinatorial equivalence between plane trees, polygon subdivisions, and parenthesizations
-
Binary erasure channel
-
Binary symmetric channel
-
Diagram for a triangulated category
-
academic genealogy of Johannes De Groot and his namesake
Photography
[edit]Most of my photos here are licensed under Creative Commons Attribution Share-Alike. See Flickr for some of my other photos, and my web site for almost all of them; if it's not listed here, it's probably not yet publically licensed, but I may be willing to share anyway.
Mendocino County
[edit]-
Little River beach
-
Cleone Groceries
-
Jug Handle Beach
-
Mendocino Beacon building
Orange County
[edit]-
Bridge across North Lake, Woodbridge, Irvine, California
-
Bren Hall at UCI
-
Social Ecology at UCI
-
Science Plaza at UCI
Theoretical computer scientists
[edit]-
Knuth Prize presentation to Volker Strassen
-
Volker Strassen giving the Knuth Prize lecture
Wall poems in Leiden
[edit]Miscellaneous
[edit]-
"Balancing", by John Hooper
-
Campbell Hall, UIUC