Publications with Elena Mumford
- Edges and switches, tunnels and bridges.
D. Eppstein, M. van Kreveld, E. Mumford, and B. Speckmann.
23rd European Workshop on Computational Geometry (EWCG'07), Graz, 2007.
10th Worksh. Algorithms and Data Structures, Halifax, Nova Scotia, 2007.
Springer, Lecture Notes in Comp. Sci. 4619, 2007, pp. 77–88.
Tech. Rep. UU-CS-2007-042, Utrecht Univ., Dept. of Information and Computing Sciences, 2007.
arXiv:0705.0413.
Comp. Geom. Theory & Applications 42 (8): 790–802, 2009 (special issue for EWCG'07).We show how to solve several versions of the problem of casing graph drawings: that is, given a drawing, choosing to draw one edge as upper and one lower at each crossing in order to improve the drawing's readability.
- Self-overlapping curves revisited.
D. Eppstein and E. Mumford.
arXiv:0806.1724.
20th ACM-SIAM Symp. Discrete Algorithms, New York, 2009, pp. 160–169.
We consider problems of determining when a curve in the plane is the projection of a 3d surface with no vertical tangents. Several problems of this type are NP-complete, but can be solved in polynomial time if a casing of the curve is also given.
- 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".
- 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)
- Steinitz theorems for orthogonal polyhedra.
D. Eppstein and E. Mumford.
arXiv:0912.0537.
26th Eur. Worksh. Comp. Geom., Dortmund, Germany, 2010.
26th ACM Symp. Comp. Geom., Snowbird, Utah, 2010, pp. 429–438.
J. Computational Geometry 5 (1): 179–244, 2014.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".
(Slides)
- Optimal 3D angular resolution for low-degree graphs.
D. Eppstein, M. Löffler, E. Mumford, and M. Nöllenburg.
Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010.
Springer, Lecture Notes in Comp. Sci. 6502, 2011, pp. 208–219.
arXiv:1009.0045.
J. Graph Algorithms and Applications 17 (3): 173–200, 2013.We show how to draw any graph of maximum degree three in three dimensions with 120 degree angles at each vertex or bend, and any graph of maximum degree four in three dimensions with the angles of the diamond lattice at each vertex or bend. In each case there are no crossings and the number of bends per edge is a small constant.
- 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".