Partial cubes and media theory
- Algorithms for media.
D. Eppstein and J.-C. Falmagne.
arXiv:cs.DS/0206033.
Int. Conf. Ordinal and Symbolic Data Analysis, Irvine, 2003.
Discrete Applied Mathematics 156 (8): 1308–1320, 2008.Falmagne recently introduced the concept of a medium, a combinatorial object encompassing hyperplane arrangements, topological orderings, acyclic orientations, and many other familiar structures. We find efficient solutions for several algorithmic problems on media: finding short reset sequences, shortest paths, testing whether a medium has a closed orientation, and listing the states of a medium given a black-box description.
- The lattice dimension of a graph.
D. Eppstein.
arXiv:cs.DS/0402028.
Eur. J. Combinatorics 26 (6): 585–592, 2005.Describes a polynomial time algorithm for isometrically embedding graphs into an integer lattice of the smallest possible dimension. The technique involves maximum matching in an auxiliary graph derived from a partial cube representation of the input.
- Algorithms for drawing media.
D. Eppstein.
arXiv:cs.DS/0406020.
12th Int. Symp. Graph Drawing, New York, 2004.
Springer, Lecture Notes in Comp. Sci. 3383, 2004, pp. 173–183.We describe two algorithms for finding planar layouts of partial cubes: one based on finding the minimum-dimension lattice embedding of the graph and then projecting the lattice onto the plane, and the other based on representing the graph as the planar dual to a weak pseudoline arrangement.
Due to editorial mishandling there will be no journal version of this paper: I submitted it to a journal in 2004, the reviews were supposedly sent back to me in 2005, but I didn't receive them and didn't respond to them, leading the editors to assume that I intended to withdraw the submission. Large portions of the paper have since been incorporated into my book Media Theory, making journal publication moot.
- Cubic partial cubes from simplicial arrangements.
D. Eppstein.
arXiv:math.CO/0510263.
Electronic J. Combinatorics 13(1), Paper R79, 2006.We show how to construct a cubic partial cube from any simplicial arrangement of lines or pseudolines in the projective plane. As a consequence, we find nine new infinite families of cubic partial cubes as well as many sporadic examples.
- Upright-quad drawing of \(st\)-planar learning spaces.
D. Eppstein.
arXiv:cs.CG/0607094.
14th Int. Symp. Graph Drawing, Karlsruhe, Germany, 2006.
Springer, Lecture Notes in Comp. Sci. 4372, 2007, pp. 282–293.
J. Graph Algorithms and Applications 12 (1): 51–72, 2008 (special issue for GD'06).We consider graph drawing algorithms for learning spaces, a type of \(st\)-oriented partial cube derived from antimatroids and used to model states of knowledge of students. We show how to draw any \(st\)-planar learning space so all internal faces are convex quadrilaterals with the bottom side horizontal and the left side vertical, with one minimal and one maximal vertex. Conversely, every such drawing represents an \(st\)-planar learning space. We also describe connections between these graphs and arrangements of translates of a quadrant.
- Happy endings for flip graphs.
D. Eppstein.
arXiv:cs.CG/0610092.
23rd ACM Symp. Comp. Geom., Gyeongju, South Korea, 2007, pp. 92–101.
J. Computational Geometry 1 (1): 3–28, 2010.We show that the triangulations of a finite point set form a flip graph that can be embedded isometrically into a hypercube, if and only if the point set has no empty convex pentagon. Point sets of this type include convex subsets of lattices, points on two lines, and several other infinite families. As a consequence, flip distance in such point sets can be computed efficiently.
- Manhattan orbifolds.
D. Eppstein.
arXiv:math.MG/0612109.
Topology and its Applications 157 (2): 494–507, 2009.We investigate a class of metrics for 2-manifolds in which, except for a discrete set of singular points, the metric is locally isometric to an L1 metric, and show that with certain additional conditions such metrics are injective. We use this construction to find the tight span of squaregraphs and related graphs, and we find an injective metric that approximates the distances in the hyperbolic plane analogously to the way the rectilinear metrics approximate the Euclidean distance.
- On verifying and engineering the well-gradedness of a
union-closed family.
D. Eppstein, J.-C. Falmagne, and H. Uzun.
arXiv:0704.2919.
38th Meeting of the European Mathematical Psychology Group, Luxembourg, 2007.
J. Mathematical Psychology 53 (1): 34–39, 2009.We describe tests for whether the union-closure of a set family is well-graded, and algorithms for finding a minimal well-graded union-closed superfamily of a given set family.
- Recognizing partial cubes in quadratic time.
D. Eppstein.
arXiv:0705.1025.
19th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 2008, pp. 1258–1266.
J. Graph Algorithms and Applications 15 (2): 269–293, 2011.We show how to test whether a graph is a partial cube, and if so embed it isometrically into a hypercube, in time O(n2), improving previous O(nm)-time solutions; here n is the number of vertices and m is the number of edges. The ideas are to use bit-parallelism to speed up previous approaches to the embedding step, and to verify that the resulting embedding is isometric using an all-pairs shortest path algorithm from "algorithms for media".
(slides)
- Geometry of partial cubes.
D. Eppstein.
Invited talk at 6th Slovenian International Conference on Graph Theory, Bled, Slovenia, 2007.I survey some of my recent results on geometry of partial cubes, including lattice dimension, graph drawing, cubic partial cubes, and partial cube flip graphs of triangulations.
(Slides)
- Media Theory: Interdisciplinary Applied Mathematics.
D. Eppstein, J.-C. Falmagne, and S. Ovchinnikov.
Springer, 2007, ISBN 978-3-540-71696-9.Many combinatorial structures such as the set of acyclic orientations of a graph, weak orderings of a set of elements, or chambers of a hyperplane arrangement have the structure of a partial cube, a graph in which vertices may be labeled by bitvectors in such a way that graph distance equals Hamming distance. This book analyzes these structures in terms of operations that change one vertex to another by flipping a single bit of the bitvector labelings. It incorporates material from several of my papers including "Algorithms for Media", "Algorithms for Drawing Media", "Upright-Quad Drawing of st-Planar Learning Spaces", and "The Lattice Dimension of a Graph".
(Publisher's web site – Reinhard Suck's review in J. Math. Psych. – Reinhard Suck's review in MathSciNet)
- Learning sequences.
D. Eppstein.
arXiv:0803.4030.
How to implement an antimatroid, with applications in computerized education.
- Isometric diamond subgraphs.
D. Eppstein.
arXiv:0807.2218.
Proc. 16th Int. Symp. Graph Drawing, Heraklion, Crete, 2008.
Springer, Lecture Notes in Comp. Sci. 5417, 2009, pp. 384–389.
We describe polynomial time algorithms for determining whether an undirected graph may be embedded in a distance-preserving way into the hexagonal tiling of the plane, the diamond structure in three dimensions, or analogous structures in higher dimensions. The graphs that may be embedded in this way form an interesting subclass of the partial cubes.
(Slides)
- Area-universal rectangular layouts.
D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek.
arXiv:0901.3924.
25th Eur. Worksh. Comp. Geom., Brussels, Belgium, 2009.
25th ACM Symp. Comp. Geom., Aarhus, Denmark, 2009, pp. 267–276.A partition of a rectangle into smaller rectangles is "area-universal" if any vector of areas for the smaller rectangles can be realized by a combinatorially equivalent partition. These partitions may be applied, for instance, to cartograms, stylized maps in which the shapes of countries have been distorted so that their areas represent numeric data about the countries. We characterize area-universal layouts, describe algorithms for finding them, and discuss related problems. The algorithms for constructing area-universal layouts are based on the distributive lattice structure of the set of all layouts of a given dual graph.
Merged with "Orientation-constrained rectangular layouts" to form the journal version, "Area-universal and constrained rectangular layouts".
- The Fibonacci dimension of a graph.
S. Cabello, D. Eppstein, and S. Klavžar.
IMFM Preprint 1084, Institute of Mathematics, Physics and Mechanics, Univ. of of Ljubljana, 2009.
arXiv:0903.2507.
Electronic J. Combinatorics 18(1), Paper P55, 2011.We investigate isometric embeddings of other graphs into Fibonacci cubes, graphs formed from the families of fixed-length bitstrings with no two consecutive ones.
- Orientation-constrained rectangular layouts.
D. Eppstein and E. Mumford.
arXiv:0904.4312.
Algorithms and Data Structures Symposium (WADS), Banff, Canada.
Springer, Lecture Notes in Comp. Sci. 5664, 2009, pp. 266–277.We show how to find a stylized map in which regions have been replaced by rectangles, preserving adjacencies between regions, with constraints on the orientations of adjacencies between regions. For an arbitrary dual graph representing a set of adjacencies, and an arbitrary set of orientation constraints, we can determine whether there exists a rectangular map satisfying those constraints in polynomial time. The algorithm is based on a representation of the set of all layouts for a given dual graph as a distributive lattice, and on Birkhoff's representation theorem for distributive lattices.
Merged with "Area-universal rectangular layouts" to form the journal version, "Area-universal and constrained rectangular layouts".
(Slides)
- Combinatorics and geometry of finite and infinite squaregraphs.
H.-J. Bandelt, V. Chepoi, and D. Eppstein.
arXiv:0905.4537.
SIAM J. Discrete Math. 24 (4): 1399–1440, 2010.Characterizes squaregraphs as duals of triangle-free hyperbolic line arrangements, provides a forbidden subgraph characterization of them, describes an algorithm for finding minimum subsets of vertices that generate the whole graph by medians, and shows that they may be isometrically embedded into Cartesian products of five (but not, in general, fewer than five) trees.
- Optimal angular resolution for face-symmetric drawings.
D. Eppstein and K. Wortman.
arXiv:0907.5474.
J. Graph Algorithms and Applications 15 (4): 551–564, 2011.We consider drawings of planar partial cubes in which all interior faces are centrally symmetric convex polygons, as in my previous paper Algorithms for Drawing Media. Among all drawings of this type, we show how to find the one with optimal angular resolution. The solution involves a transformation from the problem into the parametric negative cycle detection problem: given a graph in which the edge weights are linear functions of a parameter λ, find the minimum value of λ for which the graph contains no negative cycles.
- Ramified rectilinear polygons: coordinatization by dendrons.
H.-J. Bandelt, V. Chepoi, and D. Eppstein.
arXiv:1005.1721.
Disc. Comp. Geom. 54 (4): 771–797, 2015.
We characterize the graphs that can be isometrically embedded into the Cartesian product of two trees (partial double dendrons), and the metric spaces obtained as the median complexes of these graphs. These spaces include the space of geodesic distance in axis-parallel polygons in the L1 plane, hence the title. An algorithm based on lexicographic breadth-first search can be used to recognize partial double dendrons in linear time.
- Area-universal and constrained rectangular layouts.
D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek.
SIAM J. Computing 41 (3): 537–564, 2012.A combined journal version of "Area-universal rectangular layouts" and "Orientation-constrained rectangular layouts".
- Antimatroids and balanced pairs.
D. Eppstein.
arXiv:1302.5967.
Order 31 (1): 81–99, 2014. Erratum (with V. Wiechert).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.
- Knowledge Spaces: Applications in Education.
J.-C. Falmagne, D. Albert, C. Doble, D. Eppstein, and X. Hu, eds.
Springer, 2013.This edited volume collects experiences with automated learning systems based on the theory of knowledge spaces, and mathematical explorations of the theory of knowledge spaces and their efficient implementation.
- Learning sequences: an efficient data structure for learning spaces.
D. Eppstein.
In Knowledge Spaces: Applications in Education, J.-C. Falmagne, D. Albert, C. Doble, D. Eppstein, and X. Hu, eds.
Springer, 2013, pp. 287–304.We show how to represent a learning space by a small family of learning sequences, orderings of the items in a learning sequence that are consistent with their prerequisite relations. This representation allows for the rapid generation of the family of all consistent knowledge states and the efficient assessment of the state of knowledge of a human learner.
- Projection, decomposition, and adaption of learning spaces.
D. Eppstein.
In Knowledge Spaces: Applications in Education, J.-C. Falmagne, D. Albert, C. Doble, D. Eppstein, and X. Hu, eds.
Springer, 2013, pp. 305–322.In another chapter of the same book we used learning sequences to represent learning spaces and perform efficient knowledge assessment of a human learning. In this chapter we show how to use the same data structure to build learning spaces on a sample of the items of a larger learning space (an important subroutine in knowledge assessment) and to modify a learning space to more accurately model students.
- Structures in solution spaces: Three lessons from Jean-Claude.
D. Eppstein.
Invited talk, Conference on Meaningfulness and Learning Spaces: A Tribute to the Work of Jean-Claude Falmagne
Irvine, California, 2014.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.