Biblio Discovery — Demo Discovery Service

22 results for "David Eppstein"

Showing 1–20 · 0.82 seconds · RSS

  1. Journal Article

    Optimally fast incremental Manhattan plane embedding and planar tight span construction

    David Eppstein

    Journal of Computational Geometry, Vol. 2 No. 1 · 2011 · English · DOAJ Scopus

    We describe a data structure, a rectangular complex, that can be used represent hyperconvex metric spaces that have the same topology (although not necessarily the same distance function) as subsets of the plane. We show how to use this data structure to construct the tight span of a metric space…

    Also available at: DOAJ

  2. Journal Article

    The Complexity of Iterated Reversible Computation

    David Eppstein

    TheoretiCS, Vol. Volume 2 · 2023 · English · DOAJ Scopus

    We study a class of functional problems reducible to computing $f^{(n)}(x)$ for inputs $n$ and $x$, where $f$ is a polynomial-time bijection. As we prove, the definition is robust against variations in the type of reduction used in its definition, and in whether we require $f$ to have a…

  3. Journal Article

    Happy endings for flip graphs

    David Eppstein

    Journal of Computational Geometry, Vol. 1 No. 1 · 2010 · English · DOAJ Scopus

    We show that the triangulations of a finite point set form a flip graph that can be embedded isometrically into a hypercube, if and only if the point set has no empty convex pentagon. Point sets with no empty pentagon include intersections of lattices with convex sets, points on two lines, and…

  4. Journal Article

    Maximizing the sum of radii of disjoint balls or disks

    David Eppstein

    Journal of Computational Geometry, Vol. 8 No. 1 · 2017 · English · DOAJ Scopus

    Finding nonoverlapping balls with given centers in any metric space, maximizing the sum of radii of the balls, can be expressed as a linear program. Its dual linear program expresses the problem of finding a minimum-weight set of cycles (allowing 2-cycles) covering all vertices in a complete…

  5. Journal Article

    Realization and connectivity of the graphs of origami flat foldings

    David Eppstein

    Journal of Computational Geometry, Vol. 10 No. 1 · 2019 · English · DOAJ Scopus

    We investigate the graphs formed from the vertices and creases of an origami pattern that can be folded flat along all of its creases. As we show, this is possible for a tree if and only if the internal vertices of the tree all have even degree greater than two. However, we prove that (for…

  6. Journal Article

    Cubic planar graphs that cannot be drawn on few lines

    David Eppstein

    Journal of Computational Geometry, Vol. 12 No. 1 · 2021 · English · DOAJ Scopus

    For every integer $\ell$, we construct a cubic 3-vertex-connected planar bipartite graph $G$ with $O(\ell^3)$ vertices such that there is no planar straight-line drawing of $G$ whose vertices all lie on $\ell$ lines. This strengthens previous results on graphs that cannot be drawn on few lines…

  7. Journal Article

    Non-Euclidean Erdős–Anning theorems

    David Eppstein

    Journal of Computational Geometry, Vol. 17 No. 2 · 2026 · English · DOAJ Scopus

    The Erdős–Anning theorem states that every point set in the Euclidean plane with integer distances must be either collinear or finite. More strongly, for any (non-degenerate) triangle of diameter $\delta$, at most $O(\delta^2)$ points can have integer distances from all three triangle vertices. We…

  8. Journal Article

    Locked and Unlocked Smooth Embeddings of Surfaces

    David Eppstein

    Computing in Geometry and Topology, Vol. 2 No. 2 · 2023 · English · DOAJ

    We study the continuous motion of smooth isometric embeddings of a planar surface in three-dimensional Euclidean space, and two related discrete analogues of these embeddings: polygonal embeddings and flat foldings without interior vertices, under continuous changes of the embedding or folding…

  9. Journal Article

    The Widths of Strict Outerconfluent Graphs

    David Eppstein

    Discrete Mathematics & Theoretical Computer Science, Vol. vol. 26:3 No. Graph Theory · 2024 · English · DOAJ Scopus

    Strict outerconfluent drawing is a style of graph drawing in which vertices are drawn on the boundary of a disk, adjacencies are indicated by the existence of smooth curves through a system of tracks within the disk, and no two adjacent vertices are connected by more than one of these smooth…

  10. Journal Article

    Steinitz theorems for simple orthogonal polyhedra

    David Eppstein; Elena Mumford

    Journal of Computational Geometry, Vol. 5 No. 1 · 2014 · English · DOAJ Scopus

    We define a simple orthogonal polyhedron to be a three-dimensional polyhedron with the topology of a sphere in which three mutually-perpendicular edges meet at each vertex.By analogy to Steinitz's theorem characterizing the graphs of convex polyhedra, we find graph-theoretic characterizations of…

  11. Journal Article

    On the Complexity of Embedding in Graph Products

    Therese Biedl; David Eppstein; Torsten Ueckerdt

    Computing in Geometry and Topology, Vol. 4 No. 2 · 2025 · English · DOAJ

    Graph embedding, especially as a subgraph of a grid, is an old topic in VLSI design and graph drawing. In this paper, we investigate related questions concerning the complexity of embedding a graph G in a host graph that is the strong product of a path P with a graph H that satisfies some…

  12. Journal Article

    Approximate greedy clustering and distance selection for graph metrics

    David Eppstein; Sariel Har-Peled; Anastasios Sidiropoulos

    Journal of Computational Geometry, Vol. 11 No. 1 · 2020 · English · DOAJ Scopus

    In this paper, we consider two important problems defined on finite metric spaces, and provide efficient new algorithms and approximation schemes for these problems on inputs given as graph shortest path metrics or high-dimensional Euclidean metrics. The first of these problems is the greedy…

  13. Journal Article

    Stable-matching Voronoi diagrams: Combinatorial complexity and algorithms

    Gill Barequet; David Eppstein; Michael Goodrich et al.

    Journal of Computational Geometry, Vol. 11 No. 1 · 2020 · English · DOAJ Scopus

    We study algorithms and combinatorial complexity bounds for stable-matching Voronoi diagrams, where a set, $S$, of $n$ point sites in the plane determines a stable matching between the points in $\mathbb{R}^2$ and the sites in $S$ such that (i) the points prefer sites closer to them and sites…

  14. Journal Article

    Adjacency-preserving spatial treemaps

    Kevin Buchin; David Eppstein; Maarten Löffler et al.

    Journal of Computational Geometry, Vol. 7 No. 1 · 2016 · English · DOAJ Scopus

    Rectangular layouts, subdivisions of an outer rectangle into smaller rectangles, have many applications in visualizing spatial information, for instance in rectangular cartograms in which the rectangles represent geographic or political regions. A spatial treemap is a rectangular layout with a…

  15. Journal Article

    Visualizing Treewidth

    Alvin Chiu; Thomas Depian; David Eppstein et al.

    Journal of Graph Algorithms and Applications, Vol. 30 No. 2 · 2026 · English · DOAJ Scopus

    A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly show that graphs have bounded pathwidth or treewidth. Our approach draws the tree decomposition or path decomposition as a…

  16. Journal Article

    Covering many points with a small-area box

    Mark de Berg; Sergio Cabello; Otfried Cheong et al.

    Journal of Computational Geometry, Vol. 10 No. 1 · 2019 · English · DOAJ Scopus

    Let $P$ be a set of $n$ points in the plane. We show how to find, for a given integer $k>0$, the smallest-area axis-parallel rectangle that covers $k$ points of $P$ in $O(nk^2 \log n+ n\log^2 n)$ time. We also consider the problem of, given a value $\alpha>0$, covering as many points of $P$ as…

  17. Journal Article

    Strict confluent drawing

    David Eppstein; Danny Holten; Maarten Löffler et al.

    Journal of Computational Geometry, Vol. 7 No. 1 · 2016 · English · DOAJ Scopus

    We define strict confluent drawing, a form of confluent drawing in which the existence of an edge is indicated by the presence of a smooth path through a system of arcs and junctions (without crossings), and in which such a path, if it exists, must be unique. We prove that it is NP-complete to…

  18. Journal Article

    Flat foldings of plane graphs with prescribed angles and edge lengths

    Zachary Abel; Erik D. Demaine; Martin L. Demaine et al.

    Journal of Computational Geometry, Vol. 9 No. 1 · 2018 · English · DOAJ Scopus

    When can a plane graph with prescribed edge lengths and prescribed angles (from among $\{0,180^\circ, 360^\circ\}$) be folded flat to lie in an infinitesimally thick line, without crossings? This problem generalizes the classic theory of single-vertex flat origami with prescribed mountain-valley…

  19. Journal Article

    Face flips in origami tessellations

    Hugo A. Akitaya; Vida Dujmović; David Eppstein et al.

    Journal of Computational Geometry, Vol. 11 No. 1 · 2020 · English · DOAJ Scopus

    Given a flat-foldable origami crease pattern $G=(V,E)$ (a straight-line drawing of a planar graph on a region of the plane) with a mountain-valley (MV) assignment $\mu:E\to\{-1,1\}$ indicating which creases in $E$ bend convexly (mountain) or concavely (valley), we may flip a face $F$ of $G$ to…