David Eppstein - Publications

Graph drawing

• Trees in TeX.
  D. Eppstein.
  TUGboat 6 (1): 31, 1985.

  This note in the TeX user's group newsletter described a set of macros for drawing trees, using TeX's boxes-and-glue mechanisms to line up the nodes at each level of the tree.

  (TeX source code – Nelson Beebe's TeX tree drawing bibliography)

• Geometric thickness of complete graphs.
  M. Dillencourt, D. Eppstein, and D. S. Hirschberg.
  6th Int. Symp. Graph Drawing, Montreal, August 1998.
  Springer, Lecture Notes in Comp. Sci. 1547, 1998, pp. 102–110.
  arXiv:math.CO/9910185.
  J. Graph Algorithms and Applications 4 (3): 5–17, 2000 (special issue for GD98).

  We define a notion of geometric thickness, intermediate between the previously studied concepts of graph thickness and book thickness: a graph has geometric thickness T if its vertices can be embedded in the plane, and its edges partitioned into T subsets, so that each subset forms a planar straight line graph. We then give upper and lower bounds on the geometric thickness of complete graphs.

• Optimal Möbius transformations for information visualization and meshing.
  M. Bern and D. Eppstein.
  arXiv:cs.CG/0101006.
  7th Worksh. Algorithms and Data Structures, Providence, Rhode Island, 2001.
  Springer, Lecture Notes in Comp. Sci. 2125, 2001, pp. 14–25.

  We give linear-time quasiconvex programming algorithms for finding a Möbius transformation of a set of spheres in a unit ball or on the surface of a unit sphere that maximizes the minimum size of a transformed sphere. We can also use similar methods to maximize the minimum distance among a set of pairs of input points. We apply these results to vertex separation and symmetry display in spherical graph drawing, viewpoint selection in hyperbolic browsing, and element size control in conformal structured mesh generation.

  (WADS talk slides)

• Separating geometric thickness from book thickness.
  D. Eppstein.
  arXiv:math.CO/0109195.

  We show that geometric thickness and book thickness are not asymptotically equivalent: for every t, there exists a graph with geometric thickness two and book thickness > t.

• Separating thickness from geometric thickness.
  D. Eppstein.
  arXiv:math.CO/0204252.
  10th Int. Symp. Graph Drawing, Irvine, 2002.
  Springer, Lecture Notes in Comp. Sci. 2528, 2002, pp. 150–161.
  In Towards a Theory of Geometric Graphs, AMS, 2004, Contemporary Math 342, J. Pach, ed., pp. 75–86.

  We show that thickness and geometric thickness are not asymptotically equivalent: for every t, there exists a graph with thickness three and geometric thickness > t. The proof uses Ramsey-theoretic arguments similar to those in "Separating book thickness from thickness".

  (GD'02 talk slides)

• Confluent drawings: visualizing non-planar diagrams in a planar way.
  M. Dickerson, D. Eppstein, M. T. Goodrich, and J. Meng.
  arXiv:cs.CG/0212046.
  11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
  Springer, Lecture Notes in Comp. Sci. 2912, 2004, pp. 1–12.
  J. Graph Algorithms and Applications (special issue for GD'03) 9 (1): 31–52, 2005.

  We describe a new method of drawing graphs, based on allowing the edges to be merged together and drawn as "tracks" (similar to train tracks). We present heuristics for finding such drawings based on my previous algorithms for finding maximal bipartite subgraphs, prove that several important families of graphs have confluent drawings, and provide examples of other graphs that can not be drawn in this way.

• Quasiconvex programming.
  D. Eppstein.
  Invited talk at DIMACS Worksh. on Geometric Optimization, New Brunswick, NJ, 2003.
  Plenary talk at ALGO 2004, Bergen, Norway, 2004.
  arXiv:cs.CG/0412046.
  Combinatorial and Computational Geometry, Goodman, Pach, and Welzl, eds., MSRI Publications 52, 2005, pp. 287–331.

  Defines quasiconvex programming, a form of generalized linear programming in which one seeks the point minimizing the pointwise maximum of a collection of quasiconvex functions. Surveys algorithms for solving quasiconvex programs either numerically or via generalizations of the dual simplex method from linear programming, and describe varied applications of this geometric optimization technique in meshing, scientific computation, information visualization, automated algorithm analysis, and robust statistics.

  (DIMACS talk slides – ALGO talk slides)

• Testing bipartiteness of geometric intersection graphs.
  D. Eppstein.
  arXiv:cs.CG/0307023.
  15th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 2004, pp. 853–861.
  ACM Trans. Algorithms 5(2):15, 2009.

  We consider problems of partitioning sets of geometric objects into two subsets, such that no two objects within the same subset intersect each other. Typically, such problems can be solved in quadratic time by constructing the intersection graph and then applying a graph bipartiteness testing algorithm; we achieve subquadratic times for general objects, and O(n log n) times for balls in R^d or simple polygons in the plane, by using geometric data structures, separator based divide and conquer, and plane sweep techniques, respectively. We also contrast the complexity of bipartiteness testing with that of connectivity testing, and provide evidence that for some classes of object, connectivity is strictly harder due to a computational equivalence with Euclidean minimum spanning trees.

  (SODA talk slides)

• Selected open problems in graph drawing.
  F. J. Brandenburg, D. Eppstein, M. T. Goodrich, S. G. Kobourov, G. Liotta, and P. Mutzel.
  11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
  Springer, Lecture Notes in Comp. Sci. 2912, 2004, pp. 515–539.

  We survey a number of open problems in theoretical and applied graph drawing.

• The geometric thickness of low degree graphs.
  C. Duncan, D. Eppstein, and S. Kobourov.
  arXiv:cs.CG/0312056.
  20th ACM Symp. Comp. Geom., Brooklyn, 2004, pp. 340–346.

  We show that graphs with maximum degree four have geometric thickness at most two, by partitioning them into degree two subgraphs and applying simultaneous embedding techniques.

• 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.

  (GD04 talk slides)

• Confluent layered drawings.
  D. Eppstein, M. T. Goodrich, and J. Meng.
  12th Int. Symp. Graph Drawing, New York, 2004.
  Springer, Lecture Notes in Comp. Sci. 3383, 2004, pp. 184–194.
  arXiv:cs.CG/0507051.
  Algorithmica 47 (4): 439–452 (special issue for Graph Drawing), 2007.

  Describes a graph drawing technique combining ideas of confluent drawing with Sugiyama-style layered drawing. Uses a reduction to graph coloring to find and visualize sets of bicliques in each layer.

• Delta-confluent drawings.
  D. Eppstein, M. T. Goodrich, and J. Meng.
  13th Int. Symp. Graph Drawing, Limerick, Ireland, 2005.
  Springer, Lecture Notes in Comp. Sci. 3843, 2006, pp. 165–176.
  arXiv:cs.CG/0510024.
  

  We characterize the graphs that can be drawn confluently with a single confluent track that is tree-like except for three-way Delta junctions, as being exactly the distance hereditary graphs. Based on this characterization, we develop efficient algorithms for drawing these graphs.

  (GD'05 talk slides)

• Drawings of planar graphs with few slopes and segments.
  V. Dujmović, D. Eppstein, M. Suderman, and D. R. Wood.
  arXiv:math.CO/0606450.
  Comp. Geom. Theory & Applications 38: 194–212, 2007.

  We study straight-line drawings of planar graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees. We prove that every 3-connected plane graph on n vertices has a plane drawing with at most 5n/2 segments and at most 2n slopes. We prove that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface).

• 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.

  (GD'06 talk slides)

• Trees with convex faces and optimal angles.
  J. Carlson and D. Eppstein.
  arXiv:cs.CG/0607113.
  14th Int. Symp. Graph Drawing, Karlsruhe, Germany, 2006.
  Springer, Lecture Notes in Comp. Sci. 4372, 2007, pp. 77–88.

  We consider drawings of trees which, if the leaf edges were extended to infinite rays, would form partitions of the plane into unbounded convex polygons. For such a drawing the edges may be chosen independently without any possibility of edge crossing. We show how to choose the angles of such drawings to optimize the angular resolution of the drawing.

  (GD06 talk slides)

• Choosing colors for geometric graphs via color space embeddings.
  M. Dillencourt, D. Eppstein, and M. T. Goodrich.
  arXiv:cs.CG/0609033.
  14th Int. Symp. Graph Drawing, Karlsruhe, Germany, 2006.
  Springer, Lecture Notes in Comp. Sci. 4372, 2007, pp. 294–305.

  We show how to choose colors for the vertices of a graph drawing in such a way that all colors are easily distinguishable, but such that adjacent vertices have especially dissimilar colors, by considering the problem as one of embedding the graph into a three-dimensional color space.

  (GD'06 talk slides)

• 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.

  (WADS talk slides)

• The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing.
  D. Eppstein.
  arXiv:0709.4087.
  Proc. 16th Int. Symp. Graph Drawing, Heraklion, Crete, 2008.
  Springer, Lecture Notes in Comp. Sci. 5417, 2009, pp. 78–89.
  J. Graph Algorithms and Applications 17 (1): 35–55, 2013.

  Defines a class of orthogonal graph drawings formed by a point set in three dimensions for which axis-parallel line contains zero or two vertices, with edges connecting pairs of points on each nonempty axis-parallel line. Shows that the existence of such a drawing can be defined topologically, in terms of certain two-dimensional surface embeddings of the same graph. Based on this equivalence, describes algorithms, graph-theoretic properties, and hardness results for graphs of this type.

  (Slides from talk at U. Arizona, February 2008 – Slides from GD08) )

• Principles of Graph Drawing.
  D. Eppstein.
  Talk at Inst. for Mathematical Behavioral Sciences, May 2008.
  Talk at Technical University of Eindhoven, September 2008.
  
• Succinct greedy geometric routing using hyperbolic geometry.
  D. Eppstein and M. T. Goodrich.
  arXiv:0806.0341.
  Proc. 16th Int. Symp. Graph Drawing, Heraklion, Crete, 2008
  (under the different title "Succinct greedy graph drawing in the hyperbolic plane"),
  Springer, Lecture Notes in Comp. Sci. 5417, 2009, pp. 14–25.
  IEEE Transactions on Computing 60 (11): 1571–1580, 2011.

  Greedy drawing is an idea for encoding network routing tables into the geometric coordinates of an embedding of the network, but most previous work in this area has ignored the space complexity of these encoded tables. We refine a method of R. Kleinberg for embedding arbitrary graphs into the hyperbolic plane, which uses linearly many bits to represent each vertex, and show that only logarithmic bits per point are needed.

• 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)

• 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.

• 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)

• Drawing graphs in the plane with a prescribed outer face and polynomial area.
  E. Chambers, D. Eppstein, M. T. Goodrich, and M. Löffler.
  Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010.
  Springer, Lecture Notes in Comp. Sci. 6502, 2011, pp. 129–140.
  arXiv:1009.0088.
  J. Graph Algorithms and Applications 16 (2): 243–259, 2012.

  Tutte's method of spring embeddings allows any triangulated planar graph to be drawn so that the outer face has any pre-specified convex shape, but it may place vertices exponentially close to each other. Alternative graph drawing methods provide polynomial-area straight line drawings but do not allow the outer face shape to be specified. We describe a drawing method that combines both properties: it has polynomial area, and can match any pre-specified shape of the outer face, even a shape in which some of the vertices have 180 degree angles. We apply our results to drawing polygonal schemas for graphs embedded on surfaces of positive genus.

• 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.
  Springer, Lecture Notes in Comp. Sci. 6502, 2011, pp. 195–207.
  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.
  Springer, Lecture Notes in Comp. Sci. 6502, 2011, pp. 183–194.
  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.
  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.

• Guest editor's foreword.
  D. Eppstein and E. Gansner.
  Journal of Graph Algorithms and Applications 15 (2): 3–5, 2011.
  (Special Issue on Selected Papers from the Seventeenth International Symposium on Graph Drawing, GD 2009)
  
• Confluent Hasse diagrams.
  D. Eppstein and J. Simons.
  Proc. 19th Int. Symp. Graph Drawing, Eindhoven, The Netherlands, 2011.
  Springer, Lecture Notes in Comp. Sci. 7034, 2012, pp. 2–13.
  arXiv:1108.5361.
  J. Graph Algorithms and Applications 17 (7): 689–710, 2013.

  We show that a partial order has a non-crossing upward planar drawing if and only if it has order dimension two, and we use the Dedekind-MacNeille completion to find a drawing with the minimum possible number of confluent junctions.

• Hardness of approximate compaction for nonplanar orthogonal graph drawings.
  M. J. Bannister and D. Eppstein.
  Proc. 19th Int. Symp. Graph Drawing, Eindhoven, The Netherlands, 2011.
  Springer, Lecture Notes in Comp. Sci. 7034, 2012, pp. 367–378.

  We show that, for several variants of the problem of compacting a grid drawing of a graph to use the minimum number of rows or minimum area, no good approximation algorithm is possible. We also develop fixed-parameter tractable algorithms and approximation algorithms showing that some of our inapproximability bounds are tight. See the journal version, "Inapproximability of orthogonal compaction", for some improvements and corrections.

• Planar and poly-arc Lombardi drawings.
  C. Duncan, D. Eppstein, M. T. Goodrich, S. Kobourov, and M. Löffler, and M. Nöllenburg.
  Proc. 19th Int. Symp. Graph Drawing, Eindhoven, The Netherlands, 2011.
  Springer, Lecture Notes in Comp. Sci. 7034, 2012, pp. 308–319.
  arXiv:1109.0345.
  J. Computational Geometry 9 (1): 328–355, 2018.

  We extend Lombardi drawing (in which each edge is a circular arc and the edges incident to a vertex must be equally spaced around it) to drawings in which edges are composed of multiple arcs, and we investigate the graphs that can be drawn in this more relaxed framework.

• Inapproximability of orthogonal compaction.
  M. J. Bannister, D. Eppstein, and J. Simons.
  arXiv:1108.4705.
  J. Graph Algorithms and Applications 16 (3): 651–673, 2012. (Special issue for GD 2011.)

  This is the journal version of "Hardness of approximate compaction for nonplanar orthogonal graph drawings". It has stronger inapproximability bounds, and more variations of the compaction problem that are hard to approximate. In addition it includes a retraction of a buggy approximation algorithm from the conference version.

• A Möbius-invariant power diagram and its applications to soap bubbles and planar Lombardi drawing.
  D. Eppstein.
  Invited talk at EuroGIGA Midterm Conference, Prague, Czech Republic, 2012.
  Discrete Comput. Geom. 52 (3): 515–550, 2014 (Special issue for SoCG 2013).

  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.

• Planar Lombardi drawings for subcubic graphs.
  D. Eppstein.
  arXiv:1206.6142.
  20th Int. Symp. Graph Drawing, Redmond, Washington, 2012.
  Springer, Lecture Notes in Comp. Sci. 7704, 2013, pp. 126–137.
  

  We show that every planar graph of maximum degree three has a planar Lombardi drawing and that some but not all 4-regular planar graphs have planar Lombardi drawings. The proof idea combines circle packings with a form of Möbius-invariant power diagram for circles, defined using three-dimensional hyperbolic geometry.

  For the journal version, see "A Möbius-invariant power diagram and its applications to soap bubbles and planar lombardi drawing.".

  (Slides)

• Force-directed graph drawing using social gravity and scaling.
  M. J. Bannister, D. Eppstein, M. T. Goodrich, and L. Trott.
  arXiv:1209.0748.
  20th Int. Symp. Graph Drawing, Redmond, Washington, 2012.
  Springer, Lecture Notes in Comp. Sci. 7704, 2013, pp. 414–425.
  

  We extend force-directed methods of graph drawing by adding a force that pulls vertices towards the center of the drawing, with a strength proportional to the centrality of the vertex. Gradually scaling up this force helps avoid the tangling that would otherwise result from its use.

• On the density of maximal 1-planar graphs.
  F. J. Brandenburg, D. Eppstein, A. Gleißner, M. T. Goodrich, K. Hanauer, and J. Reislhuber.
  20th Int. Symp. Graph Drawing, Redmond, Washington, 2012.
  Springer, Lecture Notes in Comp. Sci. 7704, 2013, pp. 327–338.
  

  A graph is 1-planar if it can be drawn in the plane with at most one crossing per edge, and maximal 1-planar if it is 1-planar but adding any edge would force more than one crossing on some edge or edges. Although maximal 1-planar graphs on n vertices may have as many as 4n − 8 edges, we show that there exist maximal 1-planar graphs with as few as 45n/17 + O(1) edges.

• The graphs of planar soap bubbles.
  D. Eppstein.
  arXiv:1207.3761.
  Proc. 29th ACM Symp. on Computational Geometry, Rio de Janeiro, 2013, pp. 27–36.

  We characterize the graphs of two-dimensional soap bubble clusters as being exactly the bridgeless 3-regular planar graphs. The proof uses the Möbius invariance of the properties characterizing these clusters together with our previous circle packing method for constructing Lombardi drawings of graphs.

  For the journal version, see "A Möbius-invariant power diagram and its applications to soap bubbles and planar lombardi drawing.".

  (Slides)

• Parameterized complexity of 1-planarity.
  M. J. Bannister, S. Cabello, and D. Eppstein.
  arXiv:1304.5591.
  13th Int. Symp. Algorithms and Data Structures (WADS 2013), London, Ontario
  Springer, Lecture Notes in Comp. Sci. 8037, 2013, pp. 97–108.
  J. Graph Algorithms and Applications 22 (1): 23–49, 2018. (Special issue on Graph Drawing Beyond Planarity.)
  

  We show that testing whether a graph is 1-planar (drawable with at most one crossing per edge) may be performed in polynomial and fixed-parameter tractable time for graphs of bounded circuit rank, vertex cover number, or tree-depth. However, it is NP-complete for graphs of bounded treewidth, pathwidth, or bandwidth.

  (Slides)

• A brief history of curves in graph drawing.
  D. Eppstein.
  Invited survey talk at Workshop on Drawing Graphs and Maps with Curves, Dagstuhl, Germany, April 2013.
  Drawing Graphs and Maps with Curves (Dagstuhl Seminar 13151), S. G. Kobourov, M. Nöllenburg, and M. Teillaud, eds., Dagstuhl Reports 3(4): 40–46, 2013.

  (Slides)

• Universal point sets for planar graph drawings with circular arcs.
  P. Angelini, D. Eppstein, F. Frati, M. Kaufmann, S. Lazard, T. Mchedlidze, M. Teillaud, and A. Wolff.
  HAL-Inria open archive oai:hal.inria.fr:hal-00846953.
  25th Canadian Conference on Computational Geometry, Waterloo, Canada, 2013.
  J. Graph Algorithms and Applications 18 (3): 313–324, 2014.

  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.

  (Slides)

• Fixed parameter tractability of crossing minimization of almost-trees.
  M. J. Bannister, D. Eppstein, and J. Simons.
  arXiv:1308.5741.
  21st Int. Symp. Graph Drawing, Bordeaux, France, 2013.
  Springer, Lecture Notes in Comp. Sci. 8242, 2013, pp. 340–351.
  

  Many real-world graphs are k-almost-trees for small values of k: graphs in which, in every biconnected component, removing a spanning tree leaves at most k edges. We use kernelization methods to show that in such graphs, the 1-page and 2-page crossing numbers can be computed quickly.

• Superpatterns and universal point sets.
  M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein.
  arXiv:1308.0403.
  21st Int. Symp. Graph Drawing, Bordeaux, France, 2013.
  Springer, Lecture Notes in Comp. Sci. 8242, 2013, pp. 208–219.
  Bannister's talk on this paper won the GD2013 best presentation award.
  J. Graph Algorithms & Applications 18 (2): 177–209, 2014 (special issue for GD'13).

  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 \(n^2/4\), and we also construct near-linear universal sets for graphs of bounded pathwidth.

• Drawing arrangement graphs in small grids, or how to play planarity.
  D. Eppstein.
  arXiv:1308.0066.
  21st Int. Symp. Graph Drawing, Bordeaux, France, 2013.
  Springer, Lecture Notes in Comp. Sci. 8242, 2013, pp. 436–447.
  J. Graph Algorithms & Applications 18 (2): 211–231, 2014 (special issue for GD'13).

  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 n^7/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.

• Strict confluent drawing.
  D. Eppstein, D. Holten, M. Löffler, M. Nöllenburg, and B. Speckmann, and K. Verbeek.
  arXiv:1308.6824.
  21st Int. Symp. Graph Drawing, Bordeaux, France, 2013.
  Springer, Lecture Notes in Comp. Sci. 8242, 2013, pp. 352–363.
  J. Computational Geometry 7 (1): 22–46, 2016.

  A confluent drawing of a graph is a set of points and curves in the plane with the property that two vertices are adjacent in the graph if and only if the corresponding points can be connected to each other by smooth paths in the drawing. We define a variant of confluent drawing, strict confluent drawing, in which a smooth path between two vertices (if it exists) must be unique. We show that it is NP-complete to test whether such drawings exist, in contrast to unrestricted confluence for which the complexity remains open. Additionally, we show that finding outerplanar drawings (in which the points are on the boundary of a disk and the curves are interior to it) with a fixed cyclic vertex ordering can be performed in polynomial time. We use circle packings to find nice versions of these drawings in which all tracks are represented by piecewise-circular curves.

• Convex-arc drawings of pseudolines.
  D. Eppstein, M. van Garderen, B. Speckmann, and T. Ueckerdt.
  21st Int. Symp. Graph Drawing (poster), Bordeaux, France, 2013.
  Springer, Lecture Notes in Comp. Sci. 8242, 2013, pp. 522–523.
  arXiv:1601.06865.
  

  We show that every outerplanar weak pseudoline arrangement (a collection of curves topologically equivalent to lines, each crossing at most once but possibly zero times, with all crossings belonging to an infinite face) can be straightened to a hyperbolic line arrangement. As a consequence such an arrangement can also be drawn in the Euclidean plane with each pseudoline represented as a convex piecewise-linear curve with at most two bends. In contrast, for arbitrary pseudoline arrangements, a linear number of bends is sufficient and sometimes necessary.

• Small superpatterns for dominance drawing.
  M. J. Bannister, W. E. Devanny, and D. Eppstein.
  arXiv:1310.3770.
  Analytic Algorithmics and Combinatorics (ANALCO14), Portland, Oregon, 2014, pp. 92–103.

  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(n^3/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.

• Planar induced subgraphs of sparse graphs.
  G. Borradaile, D. Eppstein, and P. Zhu.
  arXiv:1408.5939.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014.
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 1–12.
  J. Graph Algorithms & Applications 19 (1): 281–297, 2015.

  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.

• The Galois complexity of graph drawing: why numerical solutions are ubiquitous for force-directed, spectral, and circle packing drawings.
  M. J. Bannister, W. E. Devanny, D. Eppstein, and M. T. Goodrich.
  arXiv:1408.1422.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 149–161.
  J. Graph Algorithms & Applications 19 (2): 619–656, 2015 (special issue for GD'14).

  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.

• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth.
  M. J. Bannister and D. Eppstein.
  arXiv:1408.6321.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014.
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 210–221.
  J. Graph Algorithms & Applications 22 (4): 577–606, 2018.

  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.

• Balanced circle packings for planar graphs.
  M. J. Alam, D. Eppstein, M. T. Goodrich, S. Kobourov, and S. Pupyrev.
  arXiv:1408.4902.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014.
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 125–136.

  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.

• Flat foldings of plane graphs with prescribed angles and edge lengths.
  Z. Abel, E. Demaine, M. Demaine, D. Eppstein, A. Lubiw, and R. Uehara.
  arXiv:1408.6771.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014.
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 272–283.
  J. Computational Geometry 9 (1): 74–93, 2018.

  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.

• Contact graphs of circular arcs.
  M. J. Alam, D. Eppstein, M. Kaufmann, S. Kobourov, S. Pupyrev A. Schulz, and T. Ueckerdt.
  arXiv:1501.00318.
  14th Algorithms and Data Structures Symp. (WADS 2015), Victoria, BC.
  Springer, Lecture Notes in Comp. Sci. 9214 (2015), pp. 1–13.

  We study the graphs formed by non-crossing circular arcs in the plane, having a vertex for each arc and an edge for each point where an arc endpoint touches the interior of another arc.

  (Slides)

• Structure of graphs with locally restricted crossings.
  V. Dujmović, D. Eppstein, and D. R. Wood.
  arXiv:1506.04380.
  23rd Int. Symp. Graph Drawing, Los Angeles, California, 2015.
  Springer, Lecture Notes in Comp. Sci. 9411 (2015), pp. 87–98.
  SIAM J. Discrete Math. 31 (2): 805–824, 2017.

  The Graph Drawing version used the alternative title "Genus, treewidth, and local crossing number". We prove tight bounds on the treewidth of graphs embedded on low-genus surfaces with few crossings per edge, and nearly tight bounds on the number of crossings per edge for graphs with a given number of edges embedded on low-genus surfaces.

  (Slides — local copy of final version)

• Track layouts, layered path decompositions, and leveled planarity.
  M. J. Bannister, W. E. Devanny, and V. Dujmović, D. Eppstein, and D. R. Wood.
  arXiv:1506.09145.
  24th Int. Symp. Graph Drawing, Athens, Greece, 2016.
  Springer, Lecture Notes in Comp. Sci. 9801 (2016), pp. 499–510.
  Algorithmica 81 (4): 1561–1583, 2019.

  We introduce the concept of a layered path decomposition, and show that the layered pathwidth can be used to characterize the leveled planar graphs. As a consequence we show that finding the minimum number of tracks in a track layout of a given graph is NP-complete. The GD version includes only the parts concerning track layout, and uses the title "Track Layout is Hard".

• Confluent orthogonal drawings of syntax diagrams.
  M. J. Bannister, D. A. Brown, and D. Eppstein.
  arXiv:1509.00818.
  23rd Int. Symp. Graph Drawing, Los Angeles, California, 2015.
  Springer, Lecture Notes in Comp. Sci. 9411 (2015), pp. 260–271.

  We describe a system for transforming context-free grammars into human-readable syntax diagrams, including optimizations that change the structure of the grammar to make it more readable without affecting the language described by the grammar.

• Treetopes and their graphs.
  D. Eppstein.
  arXiv:1510.03152.
  27th ACM-SIAM Symp. on Discrete Algorithms, Arlington, 2016, pp. 969–984.
  Discrete Comput. Geom. 64 (2), 259–289, 2020 (special issue for Branko Grünbaum).
  

  We describe a class of polytopes of varying dimensions, whose restriction to three dimensions is the class of roofless polyhedra (Halin graphs). We call these polytopes treetopes. We show that the four-dimensional treetopes are closely related to clustered planar graph drawings, and we use this connection to recognize the graphs of four-dimensional treetopes in polynomial time.

  (Slides)

• Triangle-free penny graphs: degeneracy, choosability, and edge count.
  D. Eppstein.
  arXiv:1708.05152.
  Proc. 25th Int. Symp. Graph Drawing, Boston, Massachusetts, 2017.
  Springer, Lecture Notes in Comp. Sci. 10692 (2018), pp. 506–513.
  J. Graph Algorithms & Applications 22 (3): 483–499 (special issue for GD 2017), 2018.

  A penny graph is the contact graph of unit disks: each disk represents a vertex of the graph, no two disks can overlap, and each tangency between two disks represents an edge in the graph. We prove that, when this graph is triangle free, its degeneracy is at most two. As a consequence, triangle-free penny graphs have list chromatic number at most three. We also show that the number of edges in any such graph is at most 2n − Ω(√n). The journal version uses the alternative title "Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs".

  (Slides)

• The effect of planarization on width.
  D. Eppstein.
  arXiv:1708.05155.
  Proc. 25th Int. Symp. Graph Drawing, Boston, Massachusetts, 2017.
  Springer, Lecture Notes in Comp. Sci. 10692 (2018), pp. 560–572.
  J. Graph Algorithms & Applications 22 (3): 461–481 (special issue for GD 2017), 2018.

  We study what happens to nonplanar graphs of low width (for various width measures) when they are made planar by replacing crossings by vertices. For treewidth, pathwidth, branchwidth, clique-width, and tree-depth, this replacement can blow up the width from constant to linear. However, for bandwidth, cutwidth, and carving width, graphs of bounded width stay bounded when we planarize them.

  (Slides)

• Square-contact representations of partial 2-trees and triconnected simply-nested graphs.
  G. Da Lozzo, W. E. Devanny, D. Eppstein, and T. Johnson.
  arXiv:1710.00426.
  Proc. 28th Int. Symp. Algorithms and Computation (ISAAC 2017), Phuket, Thailand, 2017.
  Leibniz International Proceedings in Informatics (LIPIcs) 92, pp. 24:1–24:16.
  

  We show that the K_1,1,3-free partial 2-trees and the Halin graphs other than K₄ can all be represented as proper contact graphs of squares in the plane. Among partial 2-trees and Halin graphs, these are exactly the ones that can be embedded without nonempty triangles, which form an obstacle to the existence of square contact representations. However the graph of a square antiprism has no such representation despite being embeddable without any nonempty triangles.

• Subexponential-time and FPT algorithms for embedded flat clustered planarity.
  G. Da Lozzo, D. Eppstein, M. T. Goodrich, and S. Gupta.
  arXiv:1803.05465
  Proc. 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018), Lübbenau, Germany.
  Springer, Lecture Notes in Comp. Sci. 11159 (2018), pp. 111–124.

  Clustered planarity is the problem of simultaneously drawing a planar graph and a clustering of its vertices (as Jordan curves surrounding the cluster) with no unnecessary crossings between edges or cluster boundaries; it remains unknown whether it can be solved in polynomial time. We provide parameterized and subexponential exact algorithms for the case where the planar embedding is fixed and the clusters form a partition of the vertices.

• Realization and connectivity of the graphs of origami flat foldings.
  D. Eppstein.
  arXiv:1808.06013.
  Proc. 26th Int. Symp. Graph Drawing, Barcelona, 2018.
  Springer, Lecture Notes in Comp. Sci. 11282 (2018), pp. 541–554.
  J. Computational Geometry 10 (1): 257–280, 2019.

  If you fold a piece of paper flat and unfold it again, the resulting crease pattern forms a planar graph. We prove that a tree can be realized in this way (with its leaves as diverging rays that reach the boundary of the paper) if and only if all internal vertices have odd degree greater than two. On the other hand, for a folding pattern on an infinite sheet of paper with an added vertex at infinity as the endpoint of all its rays, the resulting graph must be 2-vertex-connected and 4-edge-connected.

  (Slides)

• Cubic planar graphs that cannot be drawn on few lines.
  D. Eppstein.
  arXiv:1903.05256.
  Proc. 35th Int. Symp. on Computational Geometry, Portland, Oregon, June 2019.
  Leibniz International Proceedings in Informatics (LIPIcs) 129, 2019, pp. 32:1–32:15.
  J. Computational Geometry 12 (1): 178–197, 2021.
  

  We construct planar graphs whose straight drawings require a large number of lines (at least the cube root of the number of vertices) to cover all vertices. We also find series-parallel graphs and apex-trees that require a non-constant number of lines.

  (Slides)

• Bipartite and series-parallel graphs without planar Lombardi drawings.
  D. Eppstein.
  arXiv:1906.04401.
  Proc. 31st Canadian Conference on Computational Geometry, Edmonton, Canada, 2019, pp. 17–22.
  J. Graph Algorithms & Applications 25 (1): 549–562, 2021.

  Not every bipartite planar graph has a planar Lombardi drawing. Not every plane series parallel graph has a planar Lombardi drawing with the same embedding. The proof involves the properties of cycles of circular-arc-quadrilaterals all sharing the same two vertices, with equal and sharp vertex angles.

  (Slides)

• C-planarity testing of embedded clustered graphs with bounded dual carving-width.
  G. Da Lozzo, D. Eppstein, M. T. Goodrich, and S. Gupta.
  arXiv:1910.02057.
  Proc. 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), Munich, Germany, 2019 (best paper award).
  Leibniz International Proceedings in Informatics (LIPIcs) 148, 2019, pp. 9:1–9:17.
  Algorithmica 83 (8): 2471–2502, 2021 (special issue for IPEC 2019).

  We show that finding clustered planar drawings can be done in fixed-parameter-tractable time, depending only on a single width parameter of the input clustered graph.

• Homotopy height, grid-minor height and graph-drawing height.
  T. Biedl, E. Chambers, D. Eppstein, A. de Mesmay, and T. Ophelders.
  arXiv:1908.05706.
  Proc. 27th Int. Symp. Graph Drawing, Prague, Czech Republic, 2019.
  Springer, Lecture Notes in Comp. Sci. 11904 (2019), pp. 468–481.
  

  We lower bound the height of a drawing of a planar graph in an integer grid by a topological invariant, the homotopy height, and show that this invariant is equal to the smallest height of a grid graph in which the given graph is a minor.

• Simplifying activity-on-edge graphs.
  D. Eppstein, D. Frishberg, and E. Havvaei.
  arXiv:2002.01610.
  Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020).
  Leibniz International Proceedings in Informatics (LIPIcs) 162, 2020, pp. 24:1–24:14.

  Given a partially ordered set of activities, we find in polynomial time a directed acyclic graph and a mapping from activities to its edges, such that the sequences of activities along paths in the graph are exactly the totally ordered subsets of activities in the input.

• Stack-number is not bounded by queue-number.
  V. Dujmović, D. Eppstein, R. Robert Hickingbotham, P. Morin, and D. R. Wood.
  arXiv:2011.04195.
  Combinatorica 42: 151–164, 2022.

  Stack number is also known as page number or book thickness; it is the minimum number of stacks needed so that you can process the vertices of a graph in some sequence, pushing each edge onto one of the stacks when you process its first endpoint and popping it from the same stack when you process its second endpoint. Queue number is defined in the same way using queues instead of stacks. We show that the strong products of triangular grids and high-degree stars have bounded queue number but unbounded stack number. This result disproves the Blankenship–Oporowski conjecture, according to which subdividing edges of a graph a constant number of times cannot decrease its stack number from non-constant to constant, because subdivisions of the same products also have bounded stack number. It also confirms a conjecture of Bonnet et al on the existence of graphs with bounded sparse twin-width and unbounded stack number.

• Angles of arc-polygons and Lombardi drawings of cacti.
  D. Eppstein, D. Frishberg, and M. Osegueda.
  arXiv:2107.03615.
  Proc. 33rd Canadian Conference on Computational Geometry, 2021, pp. 56–64.
  Comp. Geom. Theory & Applications 112: 101982, 2023 (special issue for CCCG 2021).
  

  We precisely characterize the triples vertex angles that are possible for arc-triangles (curved triangles made from circular arcs), and prove an existence theorem for a large class of sets of angles for arc-polygons. Our characterization allows us to prove that every cactus graph has a planar Lombardi drawing for its natural planar embedding (the embedding in which each cycle is a bounded face), but that there exist other embeddings of cacti that have no Lombardi drawing.

• Limitations on realistic hyperbolic graph drawing.
  D. Eppstein.
  arXiv:2108.07441.
  Proc. 29th Int. Symp. Graph Drawing, Tübingen, Germany, 2021.
  Springer, Lecture Notes in Comp. Sci. 12868 (2021), pp. 343–357.
  

  Graphs drawn in the hyperbolic plane can be forced to have features much closer together than unit distance, in the absolute distance scale of the plane. In particular this is true for planar drawings of maximal planar graphs or grid graphs, and for nonplanar drawings of arbitrary graphs.

  (Slides)

• Three-dimensional graph products with unbounded stack-number.
  D. Eppstein, R. Robert Hickingbotham, L. Merker, S. Norin, M. T. Seweryn, and D. R. Wood.
  arXiv:2202.05327.
  Discrete Comput. Geom. 71: 1210–1237, 2024.
  

  The strong product of any three graphs of non-constant size has unbounded book thickness. In the case of strong products of three paths, and more generally of triangulations of \(n\times n\times n\) grid graphs obtained by adding a diagonal to each square of the grid, the book thickness is \(\Theta(n^{1/3})\). This is the first explicit example of a graph family with bounded maximum degree and unbounded book thickness.

• On the biplanarity of blowups.
  D. Eppstein.
  arXiv:2301.09246.
  Proc. 31st Int. Symp. Graph Drawing and Network Visualization, Palermo, Italy, 2023 (best paper award).
  Springer, Lecture Notes in Computer Science 14465 (part I), pp. 3–17.
  J. Graph Algorithms & Applications 28 (2): 83–99, 2024.
  

  Expanding every vertex of a planar graph to two independent copies can produce a graph of thickness greater than two, disproving a conjecture of Ellen Gethner. We also investigate special cases of this construction for which the thickness is two.

  (talk slides)

• Manipulating weights to improve stress-graph drawings of 3-connected planar graphs.
  A. Chiu, D. Eppstein, and M. T. Goodrich.
  arXiv:2307.10527.
  Proc. 31st Int. Symp. Graph Drawing and Network Visualization, Palermo, Italy, 2023.
  Springer, Lecture Notes in Computer Science 14466 (part II), pp. 141–149.

  In Tutte spring embeddings for planar graphs, it is possible to adjust the strengths of the springs and the fixed positions of the vertices on the outer face to obtain an infinite continuous family of straight-line planar embeddings. We experiment with making those adjustments to spread out the features of the drawing to better positions than they would have in the unweighted case.

• The widths of strict outerconfluent graphs.
  D. Eppstein.
  arXiv:2308.03967.
  Proc. 31st Int. Symp. Graph Drawing and Network Visualization, Palermo, Italy, 2023 (poster session).
  Springer, Lecture Notes in Computer Science 14466 (part II), pp. 244–247.
  Discrete Mathematics & Theoretical Computer Science 26 (3) 20:1–20:17, 2024.

  We construct a family of strict outerconfluent graphs with unbounded clique-width. In contrast, we use a counting argument to prove that strict outerconfluent graphs have bounded twin-width.

  (poster, proceedings summary)

• Drawing planar graphs and 1-planar graphs using cubic Bézier curves with bounded curvature.
  D. Eppstein, M. T. Goodrich, and A. M. Illickan.
  32nd International Symposium on Graph Drawing and Network Visualization.
  Leibniz International Proceedings in Informatics (LIPIcs) 320, 2024, pp. 39:1–39:17.
  arXiv:2410.12083.
  

  1-planar graphs are the graphs that can be drawn in the plane with at most one crossing per edge. We show that we can make all crossings into right angles using Bézier spline curve edges.

• Stabbing faces by a convex curve.
  D. Eppstein.
  arXiv:2508.17549.
  33rd International Symposium on Graph Drawing and Network Visualization.
  Leibniz International Proceedings in Informatics (LIPIcs) 357, 2025, pp. 29:1–29:8.
  

  For each smooth convex curve \(C\), and each planar graph \(G\), there exists a straight-line drawing of \(G\) all of whose faces are crossed by \(C\). This result serves as a counterexample to an argument that universal point sets for planar graph drawing cannot be covered by few convex polygons.

  (Slides)

• String graph obstacles of high girth and of bounded degree.
  M. Chudnovsky, D. Eppstein, and D. Fischer.
  arXiv:2509.00278.
  33rd International Symposium on Graph Drawing and Network Visualization.
  Leibniz International Proceedings in Informatics (LIPIcs) 357, 2025, pp. 24:1–24:18.
  
• Visualizing treewidth.
  A. Chiu, T. Depian, D. Eppstein, M. T. Goodrich, and M. Nöllenburg.
  arXiv:2508.19935.
  33rd International Symposium on Graph Drawing and Network Visualization.
  Leibniz International Proceedings in Informatics (LIPIcs) 357, 2025, pp. 17:1–17:20.