We provide a graph-theoretic characterization of three classes of nonconvex polyhedra with axis-parallel sides, analogous to Steinitz's theorem characterizing the graphs of convex polyhedra.
The journal version has the slightly different title "Steinitz theorems for simple orthogonal polyhedra".
We describe a recursive subdivision of the plane into quadrilaterals in the form of rhombi and kites with 60, 90, and 120 degree angles. The vertices of the resulting quadrilateral mesh form the centers of a set of circles that cross orthogonally for every two adjacent vertices, and it has many other properties that are important in finite element meshing.
This talk and journal paper combines the results from "Planar Lombardi drawings for subcubic graphs" and "The graphs of planar soap bubbles". It uses three-dimensional hyperbolic geometry to define a partition of the plane into cells with circular-arc boundaries, given an input consisting of (possibly overlapping) circular disks and disk complements, which remains invariant under Möbius transformations of the input. We use this construction as a tool to construct planar Lombardi drawings of all 3-regular planar graphs; these are graph drawings in which the edges are represented by circular arcs meeting at equal angles at each vertex. We also use it to characterize the graphs of two-dimensional soap bubble clusters as being exactly the 2-vertex-connected 3-regular planar graphs.
We generalize the 1/3-2/3 conjecture, according to which every partial order should have a pair of items that are nearly equally likely to appear in either order in a random linear extension, to antimatroids, and we prove it for several specific types of antimatroid.
We give tight bounds on the size of the largest remaining grid minor in a grid graph from which a given number of vertices have been deleted, and study several related problems.
For every positive integer n, there exists a set of n points on a parabola, with the property that every n-vertex planar graph can be drawn without crossings with its vertices at these points and with its edges drawn as circular arcs.
A superpattern of a set of permutations is a permutation that contains as a pattern every permutation in the set. Previously superpatterns had been considered for all permutations of a given length; we generalize this to sets of permutations defined by forbidden patterns; we show that the 213-avoiding permutations have superpatterns half the length of the known bound for all permutations, and that any proper permutation subclass of the 213-avoiding permutations has near-linear superpatterns. We apply these results to the construction of universal point sets, sets of points that can be used as the vertices of drawings of all n-vertex planar graphs. We use our 213-avoiding superpatterns to construct universal sets of size approximately n2/4, and we also construct near-linear universal sets for graphs of bounded pathwidth.
The planarity game involves rearranging a scrambled line arrangement graph to make it planar. We show that the resulting graphs have drawings in grids of area n7/6, much smaller than the quadratic size bound for grid drawings of planar graphs, and we provide a strategy for planarizing these graphs that is simple enough for human puzzle solving.
We construct small universal point sets for dominance drawings of classes of acyclic graphs, by finding forbidden patterns in the permutations determined by these drawings and proving the existence of small superpatterns for the permutations with these patterns forbidden. In particular, dominance drawings of the Hasse diagrams of width-2 partial orders have universal point sets of size O(n3/2), derived from superpatterns of the same size for the 321-avoiding permutations, and dominance drawings of st-planar graphs have universal point sets of size O(n log n), derived from superpatterns for riffle shuffles.
This talk surveys my work on rectangular cartograms, the 1/3-2/3 conjecture for antimatroids, and flip distance for triangulations of point sets with no empty pentagon, and how this line of research stemmed from the work of Jean-Claude Falmagne on learning spaces.
We use quadtrees to handle point location queries in an amount of time that depends on the distance of the query point to the nearest region boundary.
We study cuckoo hashing data structures in a model of flash memory in which each memory cell has a limited number of times it can be changed, so the goal is to prevent hot spots that change many times.
This paper reports on an implementation of an algorithm for constructing the configuration space of two-dimensional linkages with one degree of freedom.
We investigate the number of vertices that must be deleted from an arbitrary graph, in the worst case as a function of the number of edges, in order to planarize the remaining graph. We show that m/5.22 vertices are sufficient and m/(6 − o(1)) are necessary, and we also give bounds for the number of deletions needed to achieve certain subclasses of planar graphs.
We show that many standard graph drawing methods have algebraic solutions described by polynomials that can have unsolvable Galois groups, and that can have Galois groups whose order is divisible by large prime numbers. As a consequence certain models of exact algebraic computation are unable to construct these drawings.
We show how to express in monadic second-order logic the problems of drawing a graph with a fixed number of crossings on a one or two page book layout. By applying Courcelle's theorem, we obtain fixed-parameter tractable algorithms for these problems, parameterized by treewidth.
The balanced circle packings of the title are systems of interior-disjoint circles, whose tangencies represent the given graph, and whose radii are all within a polynomial factor of each other. We show that these packings always exist for trees, cactus graphs, outerpaths, k-outerplanar graphs of bounded degree when k is at most logarithmic, and planar graphs of bounded treedepth. The treedepth result uses a new construction of inversive-distance circle packings.
Given a plane graph with fixed edge lengths, and an assignment of the angles 0, 180, and 360 to the angles between adjacent edges, we show how to test whether the angle assignment can be realized by an embedding of the graph as a flat folding on a line. As a consequence, we can determine whether two-dimensional cell complexes with one vertex can be flattened. The main idea behind the result is to show that each face of the graph can be folded independently of the other faces.
A brief survey of algorithms for finding the k shortest paths and related k-best enumeration problems. The arXiv/EATCS version is significantly longer and with more references than the Springer version.
We consider a broad class of highest averages methods for proportional allocation (the problems of allocating seats to parties after a parliamentary election, or of allocating congressmen to states based on total population). We show that these methods can be simulated by an algorithm whose running time is proportional only to the number of parties or states, independent of the number of seats allocated or the number of voters.
A forcing set for an origami crease pattern is a subset of the folds with the property that, if these folds are folded the correct way (mountain vs valley) the rest of the pattern also has to be folded the correct way. We use a combinatorial equivalence with three-colored grids to construct minimum-cardinality forcing sets for the Miura-ori folding pattern and for other patterns with differing folds along the same line segments.
If a folding pattern for a flat origami is given, together with a mountain-valley assignment, there might still be multiple ways of folding it, depending on how some flaps of the pattern are arranged within pockets formed by folds elsewhere in the pattern. It turns out to be hard (but fixed-parameter tractable) to determine which of these ways is best with respect to minimizing the thickness of the folded pattern.
We give the first known near-linear algorithms for constructing Gomory–Hu trees of bounded-genus graphs, and we shave a log off the time for the same problem on planar graphs.
ERGMs (exponential random graph models) are used in social science to describe probability distributions on graphs that are supposed to mimic real-world social networks. However, we show that (with features that are standard in the social science application) the distributions given by these models can be computationally infeasible to sample from or to approximate the probability of seeing a given graph.
Years – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.