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 pointline incidences
[edit]
Suboptimal no3inline placement by the method of Erdős

Dual arrangement to a regular pentagon

NonDesargues 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 graphtheoretic 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

Trianglefree 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 boundeddegree planar graphs

Empty regions for the βskeleton

String graph representation of a planar graph

Ageev's 5chromatic circle graph

An intersection graph of rectangles, with boxicity two.

Hadwiger–Nelson problem: 7coloring of the plane and 4chromatic unit distance graph. From the junkyard.

A 3colored 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 zerosymmetric graph with only two edge orbits

The graph of the 33 duoprism

Paley graph of order 9 and one of its triangles

7vertex antihole graph

K_{5} subdivision of a crown graph illustrating the Kelmans–Seymour conjecture

Distinguishing coloring of a 6key keyring (6vertex cycle graph)

distinguishing coloring of a hypercube

1planar 8crossing Nauru graph

Hamiltonicity of the truncated octahedral graph

18vertex zerosymmetric graph

The unique edge coloring of G(9,2)

12vertex crown graph

Perfect matchings in a complete graph, or chord diagrams

K_{5} and K_{3,3} as minors of the Petersen graph

K_{2,2,2,2} as a 1planar 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

K_{3,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

Onecrossing drawing of K_{3,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 O_{4}

3crossing 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

Genus4 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 cubeconnected 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 M_{16}

The De Bruijn graph as a line graph

Threedimensional 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)=x^{6}

Two conjugate dessins d'enfants
Miscellaneous graph theory and graph drawing
[edit]
Graphs with a universal vertex

Optimal coloring of a split graph

15vertex planted clique in 32vertex random graph

18vertex planted clique in 64vertex random graph

A graph of cutwidth 2

K_{5} triangle packing and covering

The 2core 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

26fullerene 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 NPcompleteness

Feedback arc set

3colorings of a square, up to symmetry

3colorings 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

Cliquewidth construction

A Halin graph without any 8cycles

Pagewidth

Book crossing number

An equilibrium stress

Scorpion graph

Bidirected graph features

A 2degenerate graph and its 2core

Crossing number and 1planarity 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

Vertexface coloring

A bramble in a 3x3 grid graph

List coloring for K_{3,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 3regular 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 K_{5}

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 clawfree graphs

An augmenting path in a clawfree graph

A forbidden subgraph for comparability graphs

Thomassen's girth3 hypohamiltonian graph

Construction of a distancehereditary graph

The median graph representing the set of solutions to a 2satisfiability instance

A squaregraph

Converting a trianglefree graph into a median graph.

The Buneman graph, a median graph representing maximumparsimony 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 3trees.

A graph and its tree decomposition.

An interval graph.

Partition of the complete bipartite graph K_{4,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 5cycle 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 8cyclefree 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 nonconvex kite

The inscribed circle and extangential 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 inradius 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 radius5 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 semiellipse

Tresillo rhythm as a polygon

Convex curve through 13 grid points

Partition of a cyclic pentagon into isosceles triangles

4hexagon net for an octahedron

Partitions of a square into similar rectangles

Ordinary lines

Ambiguity in network curveshortening

Selfsimilar lens shape under curveshortening

Curveshortening of a convex curve

The grim reaper curve

Polyhedral DeltaY transformations

Visual proof of Balinski's theorem

Nonconvex pentagonal tiling

Nonconvex 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

Nonharmonic 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 345 right triangle.

Four levels of the Zcurve

Zcurve 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 fivepoint 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 unusuallyaccurate dyadic approximations

Relative error of approximations to the primecounting 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 stacksortable 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 nearlyequal legs from Pell numbers.

Divisibility of regular numbers.
Order theory
[edit]
2dimensional 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 Dih_{4}.

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

Onedimensional cyclic cellular automaton.

Twodimensional 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 3coloring

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

5vertex polyhedral Möbius strip

6vertex polyhedral strip with triangular boundary

Level sets of a crosscap

Symmetric Whitehead link

Sixcomponent "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 ShareAlike. 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