David Eppstein

According to our database1, David Eppstein authored at least 361 papers between 1985 and 2020.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2011, "For contributions to graph algorithms and computational geometry.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect.
Theor. Comput. Sci., 2020

Stable-matching Voronoi diagrams: Combinatorial complexity and algorithms.
JoCG, 2020

On the treewidth of Hanoi graphs.
CoRR, 2020

On the Edge Crossings of the Greedy Spanner.
CoRR, 2020

Simplifying Activity-On-Edge Graphs.
Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, 2020

Low-Stretch Spanning Trees of Graphs with Bounded Width.
Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, 2020

2019
Face flips in origami tessellations.
CoRR, 2019

Existence and hardness of conveyor belts.
CoRR, 2019

Some Polycubes Have No Edge-Unzipping.
CoRR, 2019

Euclidean TSP, Motorcycle Graphs, and Other New Applications of Nearest-Neighbor Chains.
CoRR, 2019

Maximum Plane Trees in Multipartite Geometric Graphs.
Algorithmica, 2019

Track Layouts, Layered Path Decompositions, and Leveled Planarity.
Algorithmica, 2019

Reconfiguring Undirected Paths.
Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

NC Algorithms for Computing a Perfect Matching, the Number of Perfect Matchings, and a Maximum Flow in One-Crossing-Minor-Free Graphs.
Proceedings of the 31st ACM on Symposium on Parallelism in Algorithms and Architectures, 2019

Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width.
Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019

New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs.
Proceedings of the 30th International Symposium on Algorithms and Computation, 2019

Tracking Paths in Planar Graphs.
Proceedings of the 30th International Symposium on Algorithms and Computation, 2019

Homotopy Height, Grid-Major Height and Graph-Drawing Height.
Proceedings of the Graph Drawing and Network Visualization - 27th International Symposium, 2019

Counting Polygon Triangulations is Hard.
Proceedings of the 35th International Symposium on Computational Geometry, 2019

Cubic Planar Graphs That Cannot Be Drawn On Few Lines.
Proceedings of the 35th International Symposium on Computational Geometry, 2019

Bipartite and Series-Parallel Graphs Without Planar Lombardi Drawings.
Proceedings of the 31st Canadian Conference on Computational Geometry, 2019

2018
The Parametric Closure Problem.
ACM Trans. Algorithms, 2018

Planar and poly-arc Lombardi drawings.
JoCG, 2018

Flat foldings of plane graphs with prescribed angles and edge lengths.
JoCG, 2018

Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs.
J. Graph Algorithms Appl., 2018

The Effect of Planarization on Width.
J. Graph Algorithms Appl., 2018

Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth.
J. Graph Algorithms Appl., 2018

Parameterized Complexity of 1-Planarity.
J. Graph Algorithms Appl., 2018

Folding Polyominoes into (Poly)Cubes.
Int. J. Comput. Geom. Appl., 2018

Minor-closed graph classes with bounded layered pathwidth.
CoRR, 2018

NC Algorithms for Perfect Matching and Maximum Flow in One-Crossing-Minor-Free Graphs.
CoRR, 2018

On the Planar Split Thickness of Graphs.
Algorithmica, 2018

From Discrepancy to Majority.
Algorithmica, 2018

Spanning Trees in Multipartite Geometric Graphs.
Algorithmica, 2018

Subexponential-Time and FPT Algorithms for Embedded Flat Clustered Planarity.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2018

Reactive Proximity Data Structures for Graphs.
Proceedings of the LATIN 2018: Theoretical Informatics, 2018

The Parameterized Complexity of Finding Point Sets with Hereditary Properties.
Proceedings of the 13th International Symposium on Parameterized and Exact Computation, 2018

Parameterized Leaf Power Recognition via Embedding into Graph Products.
Proceedings of the 13th International Symposium on Parameterized and Exact Computation, 2018

Optimally Sorting Evolving Data.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Realization and Connectivity of the Graphs of Origami Flat Foldings.
Proceedings of the Graph Drawing and Network Visualization - 26th International Symposium, 2018

Making Change in 2048.
Proceedings of the 9th International Conference on Fun with Algorithms, 2018

Faster Evaluation of Subtraction Games.
Proceedings of the 9th International Conference on Fun with Algorithms, 2018

Geometric Fingerprint Recognition via Oriented Point-Set Pattern Matching.
Proceedings of the 30th Canadian Conference on Computational Geometry, 2018

Quadratic Time Algorithms Appear to be Optimal for Sorting Evolving Data.
Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments, 2018

Grid peeling and the affine curve-shortening flow.
Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments, 2018

2017
Structure of Graphs with Locally Restricted Crossings.
SIAM J. Discret. Math., 2017

Maximizing the sum of radii of disjoint balls or disks.
JoCG, 2017

Rooted Cycle Bases.
J. Graph Algorithms Appl., 2017

Brief Announcement: Using Multi-Level Parallelism and 2-3 Cuckoo Filters for Set Intersection Queries and Sparse Boolean Matrix Multiplication.
Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, 2017

2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection.
Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2017

K-Best Solutions of MSO Problems on Tree-Decomposable Graphs.
Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

Algorithms for Stable Matching and Clustering in a Grid.
Proceedings of the Combinatorial Image Analysis - 18th International Workshop, 2017

Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs.
Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

Defining Equitable Geographic Districts in Road Networks via Stable Matching.
Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2017

Crossing Patterns in Nonplanar Road Networks.
Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2017

Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count.
Proceedings of the Graph Drawing and Network Visualization - 25th International Symposium, 2017

Forbidden Configurations in Discrete Geometry.
Proceedings of the 29th Canadian Conference on Computational Geometry, 2017

2016
k-Best Enumeration.
Encyclopedia of Algorithms, 2016

Strict confluent drawing.
JoCG, 2016

Adjacency-preserving spatial treemaps.
JoCG, 2016

Rigid origami vertices: conditions and forcing sets.
JoCG, 2016

Simple Recognition of Halin Graphs and Their Generalizations.
J. Graph Algorithms Appl., 2016

Folding a paper strip to minimize thickness.
J. Discrete Algorithms, 2016

Convex-Arc Drawings of Pseudolines.
CoRR, 2016

Covering many points with a small-area box.
CoRR, 2016

Distance-sensitive planar point location.
Comput. Geom., 2016

Cuckoo Filter: Simplification and Analysis.
Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Treetopes and their Graphs.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Models and Algorithms for Graph Watermarking.
Proceedings of the Information Security - 19th International Conference, 2016

Track Layout Is Hard.
Proceedings of the Graph Drawing and Network Visualization, 2016

All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs.
Proceedings of the 32nd International Symposium on Computational Geometry, 2016

Scheduling Autonomous Vehicle Platoons Through an Unregulated Intersection.
Proceedings of the 16th Workshop on Algorithmic Approaches for Transportation Modelling, 2016

2015
Erratum to: Antimatroids and Balanced Pairs.
Order, 2015

Metric Dimension Parameterized by Max Leaf Number.
J. Graph Algorithms Appl., 2015

Planar Induced Subgraphs of Sparse Graphs.
J. Graph Algorithms Appl., 2015

The Galois Complexity of Graph Drawing: Why Numerical Solutions are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings.
J. Graph Algorithms Appl., 2015

Improved Grid Map Layout by Point Set Matching.
Int. J. Comput. Geom. Appl., 2015

K-Best Enumeration.
Bull. EATCS, 2015

Ramified Rectilinear Polygons: Coordinatization by Dendrons.
Discret. Comput. Geom., 2015

Approximate Greedy Clustering and Distance Selection for Graph Metrics.
CoRR, 2015

D3-Reducible Graphs.
CoRR, 2015

Contact Representations of Sparse Planar Graphs.
CoRR, 2015

Near-linear-time deterministic plane Steiner spanners for well-spaced point sets.
Comput. Geom., 2015

Contact Graphs of Circular Arcs.
Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

Minimum Forcing Sets for Miura Folding Patterns.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Genus, Treewidth, and Local Crossing Number.
Proceedings of the Graph Drawing and Network Visualization - 23rd International Symposium, 2015

Confluent Orthogonal Drawings of Syntax Diagrams.
Proceedings of the Graph Drawing and Network Visualization - 23rd International Symposium, 2015

Finding All Maximal Subsequences with Hereditary Properties.
Proceedings of the 31st International Symposium on Computational Geometry, 2015

2014
Antimatroids and Balanced Pairs.
Order, 2014

Steinitz Theorems for Simple Orthogonal Polyhedra.
JoCG, 2014

Drawing Arrangement Graphs In Small Grids, Or How To Play Planarity.
J. Graph Algorithms Appl., 2014

Superpatterns and Universal Point Sets.
J. Graph Algorithms Appl., 2014

Universal Point Sets for Drawing Planar Graphs with Circular Arcs.
J. Graph Algorithms Appl., 2014

Diamond-kite adaptive quadrilateral meshing.
Eng. Comput. (Lond.), 2014

A Möbius-Invariant Power Diagram and Its Applications to Soap Bubbles and Planar Lombardi Drawing.
Discret. Comput. Geom., 2014

ERGMs are Hard.
CoRR, 2014

Grid Minors in Damaged Grids.
Electron. J. Comb., 2014

Wear Minimization for Cuckoo Hashing: How Not to Throw a Lot of Eggs into One Basket.
Proceedings of the Experimental Algorithms - 13th International Symposium, 2014

Linear-Time Algorithms for Proportional Apportionment.
Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

Balanced Circle Packings for Planar Graphs.
Proceedings of the Graph Drawing - 22nd International Symposium, GD 2014, Würzburg, 2014

Small Superpatterns for Dominance Drawing.
Proceedings of the 2014 Proceedings of the Eleventh Workshop on Analytic Algorithmics and Combinatorics, 2014

2013
Category-based routing in social networks: Membership dimension and the small-world phenomenon.
Theor. Comput. Sci., 2013

Confluent Hasse Diagrams.
J. Graph Algorithms Appl., 2013

Optimal 3D Angular Resolution for Low-Degree Graphs.
J. Graph Algorithms Appl., 2013

The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing.
J. Graph Algorithms Appl., 2013

Flows in One-Crossing-Minor-Free Graphs.
J. Graph Algorithms Appl., 2013

Listing All Maximal Cliques in Large Sparse Real-World Graphs.
ACM J. Exp. Algorithmics, 2013

On 2-Site Voronoi Diagrams Under Geometric Distance Functions.
J. Comput. Sci. Technol., 2013

Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension.
Discret. Comput. Geom., 2013

Drawing Trees with Perfect Angular Resolution and Polynomial Area.
Discret. Comput. Geom., 2013

Combinatorial Pair Testing: Distinguishing Workers from Slackers.
Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

Windows into Relational Events: Data Structures for Contiguous Subsequences of Edges.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Fixed Parameter Tractability of Crossing Minimization of Almost-Trees.
Proceedings of the Graph Drawing - 21st International Symposium, 2013

The graphs of planar soap bubbles.
Proceedings of the Symposuim on Computational Geometry 2013, 2013

Set-Difference Range Queries.
Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

Universal Point Sets for Planar Graph Drawings with Circular Arcs.
Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

Projection, Decomposition, and Adaption of Learning Spaces.
Proceedings of the Knowledge Spaces, Applications in Education, 2013

Learning Sequences: An Efficient Data Structure for Learning Spaces.
Proceedings of the Knowledge Spaces, Applications in Education, 2013

2012
Extended dynamic subgraph statistics using h-index parameterized data structures.
Theor. Comput. Sci., 2012

Area-Universal and Constrained Rectangular Layouts.
SIAM J. Comput., 2012

The h-Index of a Graph and its Application to Dynamic Subgraph Statistics.
J. Graph Algorithms Appl., 2012

Lombardi Drawings of Graphs.
J. Graph Algorithms Appl., 2012

Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area.
J. Graph Algorithms Appl., 2012

Inapproximability of Orthogonal Compaction.
J. Graph Algorithms Appl., 2012

UOBPRM: A uniformly distributed obstacle-based PRM.
Proceedings of the 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2012

Diamond-Kite Meshes: Adaptive Quadrilateral Meshing and Orthogonal Circle Packing.
Proceedings of the 21st International Meshing Roundtable, 2012

Planar Lombardi Drawings for Subcubic Graphs.
Proceedings of the Graph Drawing - 20th International Symposium, 2012

On the Density of Maximal 1-Planar Graphs.
Proceedings of the Graph Drawing - 20th International Symposium, 2012

Force-Directed Graph Drawing Using Social Gravity and Scaling.
Proceedings of the Graph Drawing - 20th International Symposium, 2012

Solving Single-Digit Sudoku Subproblems.
Proceedings of the Fun with Algorithms - 6th International Conference, 2012

Near-Linear-Time Deterministic Plane Steiner Spanners and TSP Approximation for Well-Spaced Point Sets.
Proceedings of the 24th Canadian Conference on Computational Geometry, 2012

Randomized Speedup of the Bellman-Ford Algorithm.
Proceedings of the 9th Meeting on Analytic Algorithmics and Combinatorics, 2012

2011
Straggler Identification in Round-Trip Data Streams via Newton's Identities and Invertible Bloom Filters.
IEEE Trans. Knowl. Data Eng., 2011

Succinct Greedy Geometric Routing Using Hyperbolic Geometry.
IEEE Trans. Computers, 2011

Optimally Fast Incremental Manhattan Plane Embedding and Planar Tight Span Construction.
JoCG, 2011

Optimal Angular Resolution for Face-Symmetric Drawings.
J. Graph Algorithms Appl., 2011

Guest Editor's Foreword.
J. Graph Algorithms Appl., 2011

Recognizing Partial Cubes in Quadratic Time.
J. Graph Algorithms Appl., 2011

Category-Based Routing in Social Networks: Membership Dimension and the Small-World Phenomenon (Full)
CoRR, 2011

Category-Based Routing in Social Networks: Membership Dimension and the Small-World Phenomenon (Short)
CoRR, 2011

Privacy-Enhanced Methods for Comparing Compressed DNA Sequences
CoRR, 2011

The Fibonacci Dimension of a Graph.
Electron. J. Comb., 2011

Listing All Maximal Cliques in Large Sparse Real-World Graphs.
Proceedings of the Experimental Algorithms - 10th International Symposium, 2011

Tracking Moving Objects with Few Handovers.
Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

What's the difference?: efficient set reconciliation without prior context.
Proceedings of the ACM SIGCOMM 2011 Conference on Applications, 2011

Planar and Poly-arc Lombardi Drawings.
Proceedings of the Graph Drawing - 19th International Symposium, 2011

Hardness of Approximate Compaction for Nonplanar Orthogonal Graph Drawings.
Proceedings of the Graph Drawing - 19th International Symposium, 2011

2010
Questions answered. in theory.: http://cstheory.stackexchange.com/.
SIGACT News, 2010

Combinatorics and Geometry of Finite and Infinite Squaregraphs.
SIAM J. Discret. Math., 2010

Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Edge Crossings.
SIAM J. Comput., 2010

Happy Endings for Flip Graphs.
JoCG, 2010

Approximate Weighted Farthest Neighbors and Minimum Dilation Stars.
Discrete Math., Alg. and Appl., 2010

Extended h-Index Parameterized Data Structures for Computing Dynamic Subgraph Statistics
CoRR, 2010

Densities of Minor-Closed Graph Families.
Electron. J. Comb., 2010

Paired Approximation Problems and Incompatible Inapproximabilities.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Planar Voronoi Diagrams for Sums of Convex Functions, Smoothed Distance and Dilation.
Proceedings of the Seventh International Symposium on Voronoi Diagrams in Science and Engineering, 2010

Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time.
Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

Regular Labelings and Geometric Structures.
Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

Privacy-preserving data-oblivious geometric algorithms for geographic data.
Proceedings of the 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, 2010

Cloning Voronoi Diagrams via Retroactive Data Structures.
Proceedings of the Algorithms, 2010

Steinitz theorems for orthogonal polyhedra.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

Extended Dynamic Subgraph Statistics Using h-Index Parameterized Data Structures.
Proceedings of the Combinatorial Optimization and Applications, 2010

Growth and Decay in Life-Like Cellular Automata.
Proceedings of the Game of Life Cellular Automata., 2010

2009
Approximate topological matching of quad meshes.
Vis. Comput., 2009

All maximal independent sets and dynamic dominance for sparse graphs.
ACM Trans. Algorithms, 2009

Squarepants in a tree: Sum of subtree clustering and hyperbolic pants decomposition.
ACM Trans. Algorithms, 2009

Testing bipartiteness of geometric intersection graphs.
ACM Trans. Algorithms, 2009

Finding Large Clique Minors is Hard.
J. Graph Algorithms Appl., 2009

Edges and switches, tunnels and bridges.
Comput. Geom., 2009

Curvature Aware Fundamental Cycles.
Comput. Graph. Forum, 2009

Graph-Theoretic Solutions to Computational Geometry Problems.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2009

Optimal Embedding into Star Metrics.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Orientation-Constrained Rectangular Layouts.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Self-overlapping curves revisited.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Linear-time algorithms for geometric graphs with sublinearly many crossings.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Going off-road: transversal complexity in road networks.
Proceedings of the 17th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, 2009

Area-universal rectangular layouts.
Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

Animating a continuous family of two-site Voronoi diagrams (and a proof of a bound on the number of regions).
Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

2008
Upright-Quad Drawing of st-Planar Learning Spaces.
J. Graph Algorithms Appl., 2008

Skip Quadtrees: Dynamic Data Structures for Multidimensional Point Sets.
Int. J. Comput. Geom. Appl., 2008

Algorithms for media.
Discret. Appl. Math., 2008

Dilation, smoothed distance, and minimization diagrams of convex functions
CoRR, 2008

Learning Sequences
CoRR, 2008

Motorcycle Graphs: Canonical Quad Mesh Partitioning.
Comput. Graph. Forum, 2008

Approximate topological matching of quadrilateral meshes.
Proceedings of the 2008 International Conference on Shape Modeling and Applications (SMI 2008), 2008

Studying (non-planar) road networks through an algorithmic lens.
Proceedings of the 16th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, 2008

Succinct Greedy Graph Drawing in the Hyperbolic Plane.
Proceedings of the Graph Drawing, 16th International Symposium, GD 2008, Heraklion, Crete, 2008

Isometric Diamond Subgraphs.
Proceedings of the Graph Drawing, 16th International Symposium, GD 2008, Heraklion, Crete, 2008

The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing.
Proceedings of the Graph Drawing, 16th International Symposium, GD 2008, Heraklion, Crete, 2008

Straight Skeletons of Three-Dimensional Polyhedra.
Proceedings of the Algorithms, 2008

Media theory - interdisciplinary applied mathematics.
Springer, ISBN: 978-3-540-71696-9, 2008

2007
Interconnect Criticality-Driven Delay Relaxation.
IEEE Trans. on CAD of Integrated Circuits and Systems, 2007

Foreword to special issue on SODA 2002.
ACM Trans. Algorithms, 2007

Deterministic sampling and range counting in geometric data streams.
ACM Trans. Algorithms, 2007

Improved Combinatorial Group Testing Algorithms for Real-World Problem Sizes.
SIAM J. Comput., 2007

The Traveling Salesman Problem for Cubic Graphs.
J. Graph Algorithms Appl., 2007

On Verifying and Engineering the Well-gradedness of a Union-closed Family
CoRR, 2007

Minimum dilation stars.
Comput. Geom., 2007

Drawings of planar graphs with few slopes and segments.
Comput. Geom., 2007

Confluent Layered Drawings.
Algorithmica, 2007

Space-Efficient Straggler Identification in Round-Trip Data Streams Via Newton's Identities and Invertible Bloom Filters.
Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

Guard placement for efficient point-in-polygon proofs.
Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, 2007

2006
Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms.
ACM Trans. Algorithms, 2006

The Effect of Faults on Network Expansion.
Theory Comput. Syst., 2006

Guard Placement For Wireless Localization
CoRR, 2006

Cubic Partial Cubes from Simplicial Arrangements.
Electron. J. Comb., 2006

The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems.
Proceedings of the Algorithm Theory, 2006

Single Triangle Strip and Loop on Manifolds with Boundaries.
Proceedings of the 19th Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI 2006), 2006

Upright-Quad Drawing of st -Planar Learning Spaces.
Proceedings of the Graph Drawing, 14th International Symposium, GD 2006, Karlsruhe, 2006

Choosing Colors for Geometric Graphs Via Color Space Embeddings.
Proceedings of the Graph Drawing, 14th International Symposium, GD 2006, Karlsruhe, 2006

Trees with Convex Faces and Optimal Angles.
Proceedings of the Graph Drawing, 14th International Symposium, GD 2006, Karlsruhe, 2006

2005
Memory reference caching for activity reduction on address buses.
Microprocess. Microsystems, 2005

Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way.
J. Graph Algorithms Appl., 2005

3-coloring in time O(1.3289n).
J. Algorithms, 2005

The lattice dimension of a graph.
Eur. J. Comb., 2005

Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku
CoRR, 2005

Hinged dissection of polyominoes and polyforms.
Comput. Geom., 2005

Improved Combinatorial Group Testing for Real-World Problem Sizes.
Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

Skip-webs: efficient distributed data structures for multi-dimensional data sets.
Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, 2005

Delta-Confluent Drawings.
Proceedings of the Graph Drawing, 13th International Symposium, 2005

The skip quadtree: a simple dynamic data structure for multidimensional data.
Proceedings of the 21st ACM Symposium on Computational Geometry, 2005

2004
Fast Approximation of Centrality.
J. Graph Algorithms Appl., 2004

Quasiconvex Programming
CoRR, 2004

Tiling space and slabs with acute tetrahedra.
Comput. Geom., 2004

Single-Strip Triangulation of Manifolds with Arbitrary Topology.
Comput. Graph. Forum, 2004

Quasiconvex analysis of backtracking algorithms.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Algorithms for Drawing Media.
Proceedings of the Graph Drawing, 12th International Symposium, 2004

The geometric thickness of low degree graphs.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

Lazy Algorithms for Dynamic Closest Pair with Arbitary Distance Measures.
Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, 2004

2003
Setting Parameters by Example.
SIAM J. Comput., 2003

Small Maximal Independent Sets and Faster Exact Graph Coloring.
J. Graph Algorithms Appl., 2003

Guest Editor's Foreword.
Discret. Comput. Geom., 2003

Ununfoldable polyhedra with convex faces.
Comput. Geom., 2003

Dynamic generators of topologically embedded graphs.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Möbius-invariant natural neighbor interpolation.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Selected Open Problems in Graph Drawing.
Proceedings of the Graph Drawing, 11th International Symposium, 2003

Optimized color gamuts for tiled displays.
Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

2002
The minimum expectation selection problem.
Random Struct. Algorithms, 2002

Flipping Cubical Meshes.
Eng. Comput. (Lond.), 2002

Multivariate Regression Depth.
Discret. Comput. Geom., 2002

A steady state model for graph power laws
CoRR, 2002

Moebius-Invariant Natural Neighbor Interpolation
CoRR, 2002

Beta-skeletons have unbounded dilation.
Comput. Geom., 2002

Algorithms for Coloring Quadtrees.
Algorithmica, 2002

A Steady State Model for Graph Power Law.
Proceedings of the Second International Workshop on Web Dynamics, 2002

Separating Thickness from Geometric Thickness.
Proceedings of the Graph Drawing, 10th International Symposium, 2002

Vertex-unfoldings of simplicial manifolds.
Proceedings of the 18th Annual Symposium on Computational Geometry, Barcelona, 2002

2001
The distribution of loop lengths in graphical models for turbo decoding.
IEEE Trans. Inf. Theory, 2001

Tangent Spheres and Triangle Centers.
Am. Math. Mon., 2001

Separating Geometric Thickness from Book Thickness
CoRR, 2001

Vertex-Unfoldings of Simplicial Polyhedra
CoRR, 2001

Hinged Kite Mirror Dissection
CoRR, 2001

Optimal Moebius Transformations for Information Visualization and Meshing
CoRR, 2001

Optimization over Zonotopes and Training Support Vector Machines.
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

Optimal Möbius Transformations for Information Visualization and Meshing.
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

Internet packet filter management and rectangle geometry.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Flipping Cubical Meshes.
Proceedings of the 10th International Meshing Roundtable, 2001

2000
Clustering for faster network simplex pivots.
Networks, 2000

Geometric Thickness of Complete Graphs.
J. Graph Algorithms Appl., 2000

Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs.
ACM J. Exp. Algorithmics, 2000

Incremental and Decremental Maintenance of Planar Width.
J. Algorithms, 2000

Quadrilateral Meshing by Circle Packing.
Int. J. Comput. Geom. Appl., 2000

Regression Depth and Center Points.
Discret. Comput. Geom., 2000

One-Dimensional Peg Solitaire, and Duotaire
CoRR, 2000

One-Dimensional Peg Solitaire
CoRR, 2000

3-Coloring in Time O(1.3289^n)
CoRR, 2000

Computing the Depth of a Flat
CoRR, 2000

Phutball Endgames are Hard
CoRR, 2000

Searching for Spaceships
CoRR, 2000

Diameter and Treewidth in Minor-Closed Graph Families.
Algorithmica, 2000

Spanning Trees and Spanners.
Proceedings of the Handbook of Computational Geometry, 2000

1999
Subgraph Isomorphism in Planar Graphs and Related Problems.
J. Graph Algorithms Appl., 1999

PREFACE: Festschrift for Zvi Galil.
J. Complex., 1999

Optimal Point Placement for Mesh Smoothing.
J. Algorithms, 1999

Parallel Construction of Quadtrees and Quality Triangulations.
Int. J. Comput. Geom. Appl., 1999

Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions.
Discret. Comput. Geom., 1999

The Distribution of Cycle Lengths in Graphical Models for Iterative Decoding
CoRR, 1999

Emerging Challenges in Computational Topology
CoRR, 1999

Linear complexity hexahedral mesh generation.
Comput. Geom., 1999

Shortest Paths in an Arrangement with k Line Orientations.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Hinged dissections of polyominoes and polyforms.
Proceedings of the 11th Canadian Conference on Computational Geometry, 1999

Ununfoldable polyhedra.
Proceedings of the 11th Canadian Conference on Computational Geometry, 1999

Dynamic Graph Algorithms.
Proceedings of the Algorithms and Theory of Computation Handbook., 1999

1998
Separator-Based Sparsification II: Edge and Vertex Connectivity.
SIAM J. Comput., 1998

Finding the k Shortest Paths.
SIAM J. Comput., 1998

Geometric Lower Bounds for Parametric Matroid Optimization.
Discret. Comput. Geom., 1998

The Crust and the beta-Skeleton: Combinatorial Curve Reconstruction.
Graph. Model. Image Process., 1998

On triangulating three-dimensional polygons.
Comput. Geom., 1998

Parametric and Kinetic Minimum Spanning Trees.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
Choosing Subsets with Maximum Weighted Average.
J. Algorithms, 1997

Minimum Range Balanced Cuts via Dynamic Subset Sums.
J. Algorithms, 1997

Sparsification - a technique for speeding up dynamic graph algorithms.
J. ACM, 1997

Dynamic Connectivity in Digital Images.
Inf. Process. Lett., 1997

Faster Circle Packing with Application to Non-Obtuse Triangulation.
Int. J. Comput. Geom. Appl., 1997

On Nearest-Neighbor Graphs.
Discret. Comput. Geom., 1997

Faster Geometric K-point MST Approximation.
Comput. Geom., 1997

An Efficient Algorithm for Shortest Paths in Vertical and Horizontal Segments.
Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

Faster Construction of Planar Two-Centers.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1996
Computing the Discrepancy with Applications to Supersampling Patterns.
ACM Trans. Graph., 1996

Using Sparsification for Parametric Minimum Spanning Tree Problems.
Nord. J. Comput., 1996

Separator Based Sparsification. I. Planary Testing and Minimum Spanning Trees.
J. Comput. Syst. Sci., 1996

Approximating center points with iterative Radon points.
Int. J. Comput. Geom. Appl., 1996

Average Case Analysis of Dynamic Geometric Optimization.
Comput. Geom., 1996

1995
Triangulating polygons without large angles.
Int. J. Comput. Geom. Appl., 1995

A Deterministic Linear Time Algorithm for Geometric Separators and its Applications.
Fundam. Inform., 1995

3-Coloring in time O(1.3446n): A no-MIS Algorithm
Electronic Colloquium on Computational Complexity (ECCC), 1995

Dynamic Euclidean Minimum Spanning Trees and Extrema of Binary Functions.
Discret. Comput. Geom., 1995

Algorithms for Proximity Problems in Higher Dimensions.
Comput. Geom., 1995

Asymptotic Speed-Ups in Constructive Solid Geometry.
Algorithmica, 1995

Dihedral Bounds for Mesh Generation in High Dimensions.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

The Centroid of Points with Approximate Weights.
Proceedings of the Algorithms, 1995

1994
Provably Good Mesh Generation.
J. Comput. Syst. Sci., 1994

Offline Algorithms for Dynamic Minimum Spanning Tree Problems.
J. Algorithms, 1994

Arboricity and Bipartite Subgraph Listing Algorithms.
Inf. Process. Lett., 1994

Tree-weighted neighbors and geometric k smallest spanning trees.
Int. J. Comput. Geom. Appl., 1994

Iterated Nearest Neighbors and Finding Minimal Polytopes.
Discret. Comput. Geom., 1994

Approximating the Minimum Weight Steiner Triangulation.
Discret. Comput. Geom., 1994

On the Number of Minimal 1-Steiner Trees.
Discret. Comput. Geom., 1994

Visibility with a Moving Point of View.
Algorithmica, 1994

1993
Connectivity, graph minors, and subgraph multiplicity.
Journal of Graph Theory, 1993

Improved Bounds for Intersecting Triangles and Halving Planes.
J. Comb. Theory, Ser. A, 1993

Corrigendum: Maintenance of a Minimum Spanning Forest in a Dynamic Plane Graph.
J. Algorithms, 1993

Edge Insertion for Optimal Triangulations.
Discret. Comput. Geom., 1993

Separator based sparsification for dynamic planar graph algorithms.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Computing the Discrepancy.
Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

Approximating Center Points with Iterated Radon Points.
Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

Worst-Case Bounds for Subadditive Geometric Graphs.
Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

1992
Parallel Recognition of Series-Parallel Graphs
Inf. Comput., May, 1992

Simultaneous Strong Separations of Probabilistic and Unambiguous Complexity Classes.
Math. Syst. Theory, 1992

Maintenance of a Minimum Spanning Forest in a Dynamic Plane Graph.
J. Algorithms, 1992

Sparse Dynamic Programming II: Convex and Concave Cost Functions.
J. ACM, 1992

Sparse Dynamic Programming I: Linear Cost Functions.
J. ACM, 1992

Dynamic Three-Dimensional Linear Programming.
INFORMS J. Comput., 1992

Erratum: Polynomial-size nonobtuse triangulation of polygons.
Int. J. Comput. Geom. Appl., 1992

Polynomial-size nonobtuse triangulation of polygons.
Int. J. Comput. Geom. Appl., 1992

Finding Minimum Area k-gons.
Discret. Comput. Geom., 1992

Finding the k Smallest Spanning Trees.
BIT Comput. Sci. Sect., 1992

New Algorithms for Minimum Area k-gons.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Approximating the Minimum Weight Triangulation.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Edge Insertion for Optional Triangulations.
Proceedings of the LATIN '92, 1992

Sparsification-A Technique for Speeding up Dynamic Graph Algorithms (Extended Abstract)
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Dynamic Half-Space Reporting, Geometric Optimization, and Minimum Spanning Trees
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991
Planar Orientations with Low Out-degree and Compaction of Adjacency Matrices.
Theor. Comput. Sci., 1991

The expected extremes in a Delaunay triangulation.
Int. J. Comput. Geom. Appl., 1991

The Farthest Point Delaunay Triangulation Minimizes Angles.
Comput. Geom., 1991

Efficient Sequential and Parallel Algorithms for Computing Recovery Points in Trees and Paths.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

1990
Reset Sequences for Monotonic Automata.
SIAM J. Comput., 1990

Sequence Comparison with Mixed Convex and Concave Costs.
J. Algorithms, 1990

Equipartitions of graphs.
Discret. Math., 1990

Finding the k Smallest Spanning Trees.
Proceedings of the SWAT 90, 1990

Maintenance of a Minimum Spanning Forest in a Dynamic Planar Graph.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

Sparse Dynamic Programming.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

Horizon Theorems for Lines and Polygons.
Proceedings of the Discrete and Computational Geometry: Papers from the DIMACS Special Year, 1990

1989
Parallel Algorithmic Techniques for Combinatorial Computation.
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

1988
Reset Sequences for Finite Automata with Application to Design of Parts Orienters.
Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

Speeding up Dynamic Programming
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1985
A Heuristic Approach to Program Inversion.
Proceedings of the 9th International Joint Conference on Artificial Intelligence. Los Angeles, 1985


  Loading...