73 citations · 634 across the 97 of their papers we have counts for
28 papers · 1 filter
Manipulating Weights to Improve Stress-Graph Drawings of 3-Connected Planar Graphs
Alvin Chiu, David Eppstein, Michael T. Goodrich
We study methods to manipulate weights in stress-graph embeddings to improve convex straight-line planar drawings of 3-connected planar graphs. Stress-graph embeddings are weighted…
Diamonds are Forever in the Blockchain: Geometric Polyhedral Point-Set Pattern Matching
Gill Barequet, Shion Fukuzawa, Michael T. Goodrich +3
Motivated by blockchain technology for supply-chain tracing of ethically sourced diamonds, we study geometric polyhedral point-set pattern matching as minimum-width polyhedral annu…
Euclidean TSP, Motorcycle Graphs, and Other New Applications of Nearest-Neighbor Chains
Nil Mamano, Alon Efrat, David Eppstein +5
We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We apply it to a diverse class of geometric…
Low Ply Drawings of Trees and 2-Trees
Michael T. Goodrich, Timothy Johnson
Ply number is a recently developed graph drawing metric inspired by studying road networks. Informally, for each vertex v, which is associated with a point in the plane, a disk is…
Geometric Fingerprint Recognition via Oriented Point-Set Pattern Matching
David Eppstein, Michael T. Goodrich, Jordan Jorgensen +1
Motivated by the problem of fingerprint matching, we present geometric approximation algorithms for matching a pattern point set against a background point set, where the points ha…
Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms
Gill Barequet, David Eppstein, Michael T. Goodrich +1
We study algorithms and combinatorial complexity bounds for \emph{stable-matching Voronoi diagrams}, where a set, , of point sites in the plane determines a stable matching…
Knuthian Drawings of Series-Parallel Flowcharts
Michael T. Goodrich, Timothy Johnson, Manuel Torres
Inspired by a classic paper by Knuth, we revisit the problem of drawing flowcharts of loop-free algorithms, that is, degree-three series-parallel digraphs. Our drawing algorithms s…
Balanced Circle Packings for Planar Graphs
Md. Jawaherul Alam, David Eppstein, Michael T. Goodrich +2
We study balanced circle packings and circle-contact representations for planar graphs, where the ratio of the largest circle's diameter to the smallest circle's diameter is polyno…
Force-Directed Graph Drawing Using Social Gravity and Scaling
Michael J. Bannister, David Eppstein, Michael T. Goodrich +1
Force-directed layout algorithms produce graph drawings by resolving a system of emulated physical forces. We present techniques for using social gravity as an additional force in…
Planar and Poly-Arc Lombardi Drawings
Christian A. Duncan, David Eppstein, Michael T. Goodrich +2
In Lombardi drawings of graphs, edges are represented as circular arcs, and the edges incident on vertices have perfect angular resolution. However, not every graph has a Lombardi…
Fully Retroactive Approximate Range and Nearest Neighbor Searching
Michael T. Goodrich, Joseph A. Simons
We describe fully retroactive dynamic data structures for approximate range reporting and approximate nearest neighbor reporting. We show how to maintain, for any positive constant…
Tracking Moving Objects with Few Handovers
David Eppstein, Michael T. Goodrich, Maarten Löffler
We study the online problem of assigning a moving point to a base-station region that contains it. For instance, the moving object could represent a cellular phone and the base sta…
Priority Range Trees
Michael T. Goodrich, Darren Strash
We describe a data structure, called a priority range tree, which accommodates fast orthogonal range reporting queries on prioritized points. Let be a set of points in the…
Privacy-Preserving Data-Oblivious Geometric Algorithms for Geographic Data
David Eppstein, Michael T. Goodrich, Roberto Tamassia
We give efficient data-oblivious algorithms for several fundamental geometric problems that are relevant to geographic information systems, including planar convex hulls and all-ne…
Drawing Trees with Perfect Angular Resolution and Polynomial Area
Christian A. Duncan, David Eppstein, Michael T. Goodrich +2
We study methods for drawing trees with perfect angular resolution, i.e., with angles at each node v equal to 2π/d(v). We show: 1. Any unordered tree has a crossing-free straight-l…
Cloning Voronoi Diagrams via Retroactive Data Structures
Matthew T. Dickerson, David Eppstein, Michael T. Goodrich
We address the problem of replicating a Voronoi diagram of a planar point set by making proximity queries, which are of three possible (in decreasing order of informatio…
Going Off-road: Transversal Complexity in Road Networks
David Eppstein, Michael T. Goodrich, Lowell Trott
A geometric graph is a graph embedded in the plane with vertices at points and edges drawn as curves (which are usually straight line segments) between those points. The average tr…
Succinct Greedy Geometric Routing in the Euclidean Plane
Michael T. Goodrich, Darren Strash
In greedy geometric routing, messages are passed in a network embedded in a metric space according to the greedy strategy of always forwarding messages to nodes that are closer to…
Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Edge Crossings
David Eppstein, Michael T. Goodrich, Darren Strash
We provide linear-time algorithms for geometric graphs with sublinearly many crossings. That is, we provide algorithms running in O(n) time on connected geometric graphs having n v…
Studying Geometric Graph Properties of Road Networks Through an Algorithmic Lens
David Eppstein, Michael T. Goodrich
This paper studies real-world road networks from an algorithmic perspective, focusing on empirical studies that yield useful properties of road networks that can be exploited in th…
Succinct Greedy Graph Drawing in the Hyperbolic Plane
David Eppstein, Michael T. Goodrich
We describe an efficient method for drawing any n-vertex simple graph G in the hyperbolic plane. Our algorithm produces greedy drawings, which support greedy geometric routing, so…
Straight Skeletons of Three-Dimensional Polyhedra
Gill Barequet, David Eppstein, Michael T. Goodrich +1
This paper studies the straight skeleton of polyhedra in three dimensions. We first address voxel-based polyhedra (polycubes), formed as the union of a collection of cubical (axis-…
Choosing Colors for Geometric Graphs via Color Space Embeddings
Michael B. Dillencourt, David Eppstein, Michael T. Goodrich
Graph drawing research traditionally focuses on producing geometric embeddings of graphs satisfying various aesthetic constraints. After the geometric embedding is specified, there…
Guard Placement For Wireless Localization
David Eppstein, Michael T. Goodrich, Nodari Sitchinava
Motivated by secure wireless networking, we consider the problem of placing fixed localizers that enable mobile communication devices to prove they belong to a secure region that i…