Int. Symp. Graph Drawing
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.
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".
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.".
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.
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 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.
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.
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.
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.
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.
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".
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.
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.
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.
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.
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.
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.
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.
Noncrossing longest paths and cycles.
G. Aloupis, A. Biniaz, P. Bose, J.-L. De Carufel, D. Eppstein, A. Maheshwari, S. Odak, M. Smid, C. Tóth, and P. Valtr.
32nd International Symposium on Graph Drawing and Network Visualization.
Leibniz International Proceedings in Informatics (LIPIcs) 320, 2024, pp. 36:1–36:17.
arXiv:2410.05580.
Graphs and Combinatorics 41, article 122 (25pp), 2025.The shortest path or cycle through given planar points (the solution to the traveling salesperson problem) never crosses itself: any crossing can be eliminated by a local move that shortens the tour. One might think that, correspondingly, the longest path or cycle through enough planar points always crosses itself. We show that this is not the case: there exist arbitrarily large point sets for which the longest path or cycle has no crossing.
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.
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.String graphs, the intersection graphs of curves in the plane, are closed under induced minors (induced subgraphs of contractions), and were known to have infinitely many obstacles under the induced minor order, but these obstacles were very dense. We find an infinite class of obstacles that are nearly-planar (one edge away from being planar) but we prove that there are no subcubic obstacles of high girth. Recognizing string graphs is known to be NP-complete (unusually, the hard part of this result is proving that recognition belongs to NP); we use Courcelle's theorem to give a fixed-parameter tractable algorithm for recognizing subcubic string graphs, parameterized by treewidth.
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.We experiment with metro-map style visualizations of tree decompositions of graphs. Here, the bags of a tree decomposition are visualized as stations on a metro system, and the vertices of a graph are visualized as metro lines passing through certain stations. Within each bag we display a drawing of the induced subgraph of the bag.