David Eppstein - Publications

Publications with Martin Nöllenburg

• Lombardi drawings of graphs.
  C. Duncan, D. Eppstein, M. T. Goodrich, S. Kobourov, and M. Nöllenburg.
  Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010.
  Lecture Notes in Comp. Sci. 6502, 2011, pp. 195-207, Springer-Verlag.
  arXiv:1009.0579.
  Invited talk at 7th Dutch Computational Geometry Day, Eindhoven, the Netherlands, 2010.
  J. Graph Algorithms and Applications 16(1):85-108, 2012 (special issue for GD 2010).

  In honor of artist Mark Lombardi, we define a Lombardi drawing to be a drawing of a graph in which the edges are drawn as circular arcs and at each vertex they are equally spaced around the vertex so as to achieve the best possible angular resolution. We describe algorithms for constructing Lombardi drawings of regular graphs, 2-degenerate graphs, graphs with rotational symmetry, and several types of planar graphs. A program for the rotationally symmetric case, the Lombardi Spirograph, is available online.

• Drawing trees with perfect angular resolution and polynomial area.
  C. Duncan, D. Eppstein, M. T. Goodrich, S. Kobourov, and M. Nöllenburg.
  Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010.
  Lecture Notes in Comp. Sci. 6502, 2011, pp. 183-194, Springer-Verlag.
  arXiv:1009.0581.
  Discrete Comput. Geom. 49 (2): 157-182, 2013.

  We consider balloon drawings of trees, in which each subtree of the root is drawn recursively within a disk, and these disks are arranged radially around the root, with the edges at each node spaced equally around the node so as to achieve the best possible angular resolution. If we are allowed to permute the children of each node, then we show that a drawing of this type can be made in which all edges are straight line segments and the area of the drawing is a polynomial multiple of the shortest edge length. However, if the child ordering is prescribed, exponential area might be necessary. We show that, if we relax the requirement of straight line edges and draw the edges as circular arcs (a style we call Lombardi drawing) then even with a prescribed child ordering we can achieve polynomial area.

• 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.
  Lecture Notes in Comp. Sci. 6502, 2011, pp. 208-219, Springer-Verlag.
  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.

• Adjacency-preserving spatial treemaps.
  K. Buchin, D. Eppstein, M. Löffler, M. Nöllenburg, and R. I. Silveira.
  arXiv:1105.0398.
  12th International Symposium on Algorithms and Data Structures (WADS 2011), New York, 2011.
  Lecture Notes in Comp. Sci. 6844, 2011, pp. 159-170.

  We study the recursive partitions of rectangles into sets of rectangles, and partitions of those rectangles into smaller rectangles, to form stylized visualizations of hierarchically subdivided geographic regions. There are several variations of varying difficulty depending on how much of the geographic information from the input we require the output to preserve.

Co-authors -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine

Semi-automatically filtered from a common source file.