David Eppstein

According to our database1, David Eppstein
  • authored at least 519 papers between 1985 and 2017.
  • has a "Dijkstra number"2 of three.

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

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

Grid peeling and the affine curve-shortening flow.
CoRR, 2017

Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs.
CoRR, 2017

Crossing Patterns in Nonplanar Road Networks.
CoRR, 2017

The Effect of Planarization on Width.
CoRR, 2017

Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count.
CoRR, 2017

K-Best Solutions of MSO Problems on Tree-Decomposable Graphs.
CoRR, 2017

Algorithms for Stable Matching and Clustering in a Grid.
CoRR, 2017

Defining Equitable Geographic Districts in Road Networks via Stable Matching.
CoRR, 2017

Maximum Plane Trees in Multipartite Geometric Graphs.
Proceedings of the Algorithms and Data Structures - 15th International Symposium, 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

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

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

Scheduling Autonomous Vehicle Platoons Through an Unregulated Intersection.
CoRR, 2016

Convex-Arc Drawings of Pseudolines.
CoRR, 2016

Models and Algorithms for Graph Watermarking.
CoRR, 2016

Maximizing the Sum of Radii of Disjoint Balls or Disks.
CoRR, 2016

Cuckoo Filter: Simplification and Analysis.
CoRR, 2016

Spanning Trees in Multipartite Geometric Graphs.
CoRR, 2016

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

Distance-Sensitive Planar Point Location.
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

On the Planar Split Thickness of Graphs.
Proceedings of the LATIN 2016: Theoretical Informatics, 2016

From Discrepancy to Majority.
Proceedings of the LATIN 2016: Theoretical Informatics, 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

Maximizing the Sum of Radii of Disjoint Balls or Disks.
Proceedings of the 28th Canadian Conference 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. Geometry Appl., 2015

K-Best Enumeration.
Bulletin of the EATCS, 2015

Ramified Rectilinear Polygons: Coordinatization by Dendrons.
Discrete & Computational Geometry, 2015

Rooted Cycle Bases.
CoRR, 2015

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

From Discrepancy to Majority.
CoRR, 2015

Treetopes and their Graphs.
CoRR, 2015

Metric Dimension Parameterized by Max Leaf Number.
CoRR, 2015

The Parametric Closure Problem.
CoRR, 2015

D3-Reducible Graphs.
CoRR, 2015

Genus, Treewidth, and Local Crossing Number.
CoRR, 2015

Track Layouts, Layered Path Decompositions, and Leveled Planarity.
CoRR, 2015

Confluent Orthogonal Drawings of Syntax Diagrams.
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

Folding a Paper Strip to Minimize Thickness.
Proceedings of the WALCOM: Algorithms and Computation - 9th International Workshop, 2015

Rooted Cycle Bases.
Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

The Parametric Closure Problem.
Proceedings of the Algorithms and Data Structures - 14th International Symposium, 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

Folding Polyominoes into (Poly)Cubes.
Proceedings of the 27th Canadian Conference 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.
Discrete & Computational Geometry, 2014

Wear Minimization for Cuckoo Hashing: How Not to Throw a Lot of Eggs into One Basket.
CoRR, 2014

$k$-best enumeration.
CoRR, 2014

Folding a Paper Strip to Minimize Thickness.
CoRR, 2014

Linear-time Algorithms for Proportional Apportionment.
CoRR, 2014

Planar Induced Subgraphs of Sparse Graphs.
CoRR, 2014

All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs.
CoRR, 2014

Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth.
CoRR, 2014

The Galois Complexity of Graph Drawing: Why Numerical Solutions are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings.
CoRR, 2014

ERGMs are Hard.
CoRR, 2014

Minimum Forcing Sets for Miura Folding Patterns.
CoRR, 2014

Balanced Circle Packings for Planar Graphs.
CoRR, 2014

Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths.
CoRR, 2014

Grid Minors in Damaged Grids.
Electr. 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

Planar Induced Subgraphs of Sparse Graphs.
Proceedings of the Graph Drawing - 22nd International Symposium, GD 2014, Würzburg, 2014

Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth.
Proceedings of the Graph Drawing - 22nd International Symposium, GD 2014, Würzburg, 2014

The Galois Complexity of Graph Drawing: Why Numerical Solutions Are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings.
Proceedings of the Graph Drawing - 22nd International Symposium, GD 2014, Würzburg, 2014

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

Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths.
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 Journal of Experimental 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.
Discrete & Computational Geometry, 2013

Drawing Trees with Perfect Angular Resolution and Polynomial Area.
Discrete & Computational Geometry, 2013

Combinatorial Pair Testing: Distinguishing Workers from Slackers
CoRR, 2013

Parameterized Complexity of 1-Planarity
CoRR, 2013

Grid Minors in Damaged Grids
CoRR, 2013

Strict Confluent Drawing.
CoRR, 2013

Set-Difference Range Queries.
CoRR, 2013

Drawing Arrangement Graphs In Small Grids, Or How To Play Planarity.
CoRR, 2013

Fixed parameter tractability of crossing minimization of almost-trees.
CoRR, 2013

Small Superpatterns for Dominance Drawing.
CoRR, 2013

Superpatterns and Universal Point Sets.
CoRR, 2013

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

Parameterized Complexity of 1-Planarity.
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

Strict Confluent Drawing.
Proceedings of the Graph Drawing - 21st International Symposium, 2013

Drawing Arrangement Graphs in Small Grids, or How to Play Planarity.
Proceedings of the Graph Drawing - 21st International Symposium, 2013

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

Superpatterns and Universal Point Sets.
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

Improved grid map layout by point set matching.
Proceedings of the IEEE Pacific Visualization Symposium, 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

Windows into Relational Events: Data Structures for Contiguous Subsequences of Edges
CoRR, 2012

Force-Directed Graph Drawing Using Social Gravity and Scaling
CoRR, 2012

Diamond-Kite Meshes: Adaptive Quadrilateral Meshing and Orthogonal Circle Packing
CoRR, 2012

The Graphs of Planar Soap Bubbles
CoRR, 2012

Planar Lombardi Drawings for Subcubic Graphs
CoRR, 2012

Near-Linear-Time Deterministic Plane Steiner Spanners and TSP Approximation for Well-Spaced Point Sets
CoRR, 2012

Solving Single-digit Sudoku Subproblems
CoRR, 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

Randomized Speedup of the Bellman-Ford Algorithm
CoRR, 2011

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

Planar and Poly-Arc Lombardi Drawings
CoRR, 2011

Confluent Hasse diagrams
CoRR, 2011

Hardness of Approximate Compaction for Nonplanar Orthogonal Graph Drawings
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

On 2-Site Voronoi Diagrams under Geometric Distance Functions
CoRR, 2011

Adjacency-Preserving Spatial Treemaps
CoRR, 2011

Tracking Moving Objects with Few Handovers
CoRR, 2011

Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension
CoRR, 2011

Listing All Maximal Cliques in Large Sparse Real-World Graphs
CoRR, 2011

The Fibonacci Dimension of a Graph.
Electr. 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

Adjacency-Preserving Spatial Treemaps.
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

On 2-Site Voronoi Diagrams under Geometric Distance Functions.
Proceedings of the Eighth International Symposium on Voronoi Diagrams in Science and Engineering, 2011

Confluent Hasse Diagrams.
Proceedings of the Graph Drawing - 19th International Symposium, 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

Bounds on the complexity of halfspace intersections when the bounded faces have small dimension.
Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

Category-based routing in social networks: Membership dimension and the small-world phenomenon.
Proceedings of the International Conference on Computational Aspects of Social Networks, 2011

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

Combinatorics and Geometry of Finite and Infinite Squaregraphs.
SIAM J. Discrete 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

Privacy-Preserving Data-Oblivious Geometric Algorithms for Geographic Data
CoRR, 2010

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

Drawing Trees with Perfect Angular Resolution and Polynomial Area
CoRR, 2010

Lombardi Drawings of Graphs
CoRR, 2010

Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area
CoRR, 2010

Optimal 3D Angular Resolution for Low-Degree Graphs
CoRR, 2010

Flows in One-Crossing-Minor-Free Graphs
CoRR, 2010

Regular Labelings and Geometric Structures
CoRR, 2010

Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time
CoRR, 2010

Cloning Voronoi Diagrams via Retroactive Data Structures
CoRR, 2010

Densities of Minor-Closed Graph Families.
Electr. 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

Flows in One-Crossing-Minor-Free Graphs.
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

Optimal 3D Angular Resolution for Low-Degree Graphs.
Proceedings of the Graph Drawing - 18th International Symposium, GD 2010, Konstanz, 2010

Lombardi Drawings of Graphs.
Proceedings of the Graph Drawing - 18th International Symposium, GD 2010, Konstanz, 2010

Drawing Trees with Perfect Angular Resolution and Polynomial Area.
Proceedings of the Graph Drawing - 18th International Symposium, GD 2010, Konstanz, 2010

Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area.
Proceedings of the Graph Drawing - 18th International Symposium, GD 2010, Konstanz, 2010

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

Listing all maximal cliques in sparse graphs in near-optimal time.
Proceedings of the Exact Complexity of NP-hard Problems, 31.10. - 05.11.2010, 2010

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

Approximate Weighted Farthest Neighbors and Minimum Dilation Stars.
Proceedings of the Computing and Combinatorics, 16th Annual International Conference, 2010

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

Regular labelings and geometric structures.
Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 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.
The Visual Computer, 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

Steinitz Theorems for Orthogonal Polyhedra
CoRR, 2009

Going Off-road: Transversal Complexity in Road Networks
CoRR, 2009

Paired approximation problems and incompatible inapproximabilities
CoRR, 2009

Optimally fast incremental Manhattan plane embedding and planar tight span construction
CoRR, 2009

Graph-Theoretic Solutions to Computational Geometry Problems
CoRR, 2009

Optimal Angular Resolution for Face-Symmetric Drawings
CoRR, 2009

Optimal Embedding Into Star Metrics
CoRR, 2009

Orientation-Constrained Rectangular Layouts
CoRR, 2009

On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem
CoRR, 2009

The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
CoRR, 2009

The Fibonacci dimension of a graph
CoRR, 2009

Area-Universal Rectangular Layouts
CoRR, 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. Geometry Appl., 2008

Algorithms for media.
Discrete Applied Mathematics, 2008

Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Crossings
CoRR, 2008

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

Studying (Non-Planar) Road Networks Through an Algorithmic Lens
CoRR, 2008

Isometric Diamond Subgraphs
CoRR, 2008

Finding Large Clique Minors is Hard
CoRR, 2008

Self-overlapping Curves Revisited
CoRR, 2008

Succinct Greedy Graph Drawing in the Hyperbolic Plane
CoRR, 2008

Straight Skeletons of Three-Dimensional Polyhedra
CoRR, 2008

Learning Sequences
CoRR, 2008

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

Recognizing partial cubes in quadratic time.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing
CoRR, 2007

Recognizing Partial Cubes in Quadratic Time
CoRR, 2007

Edges and Switches, Tunnels and Bridges
CoRR, 2007

Space-Efficient Straggler Identification in Round-Trip Data Streams via Newton's Identities and Invertible Bloom Filters
CoRR, 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

Edges and Switches, Tunnels and Bridges.
Proceedings of the Algorithms and Data Structures, 10th International Workshop, 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

Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

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

Happy endings for flip graphs.
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

Happy endings for flip graphs
CoRR, 2006

Choosing Colors for Geometric Graphs via Color Space Embeddings
CoRR, 2006

Trees with Convex Faces and Optimal Angles
CoRR, 2006

Upright-Quad Drawing of st-Planar Learning Spaces
CoRR, 2006

Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants Decomposition
CoRR, 2006

Guard Placement For Wireless Localization
CoRR, 2006

Approximate Weighted Farthest Neighbors and Minimum Dilation Stars
CoRR, 2006

Cubic Partial Cubes from Simplicial Arrangements.
Electr. 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.
Microprocessors and 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

Cubic Partial Cubes from Simplicial Arrangements
CoRR, 2005

Delta-confluent Drawings
CoRR, 2005

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

Confluent Layered Drawings
CoRR, 2005

Skip-Webs: Efficient Distributed Data Structures for Multi-Dimensional Data Sets
CoRR, 2005

The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data
CoRR, 2005

Improved Combinatorial Group Testing Algorithms for Real-World Problem Sizes
CoRR, 2005

The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems
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

All maximal independent sets and dynamic dominance for sparse graphs.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Minimum dilation stars.
Proceedings of the 21st ACM Symposium on Computational Geometry, 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

All Maximal Independent Sets and Dynamic Dominance for Sparse Graphs
CoRR, 2004

Algorithms for Drawing Media
CoRR, 2004

The lattice dimension of a graph
CoRR, 2004

The Effect of Faults on Network Expansion
CoRR, 2004

Single-Strip Triangulation of Manifolds with Arbitrary Topology
CoRR, 2004

Quasiconvex Programming
CoRR, 2004

Minimum Dilation Stars
CoRR, 2004

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

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

The effect of faults on network expansion.
Proceedings of the SPAA 2004: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2004

Testing bipartiteness of geometric intersection graphs.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

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

Confluent Layered Drawings.
Proceedings of the Graph Drawing, 12th International Symposium, 2004

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

Single-strip triangulation of manifolds with arbitrary topology.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

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

Deterministic sampling and range counting in geometric data streams.
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.
Discrete & Computational Geometry, 2003

Quasiconvex Analysis of Backtracking Algorithms
CoRR, 2003

The traveling salesman problem for cubic graphs
CoRR, 2003

The Geometric Thickness of Low Degree Graphs
CoRR, 2003

Deterministic Sampling and Range Counting in Geometric Data Streams
CoRR, 2003

Testing Bipartiteness of Geometric Intersection Graphs
CoRR, 2003

Tiling space and slabs with acute tetrahedra
CoRR, 2003

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

The Traveling Salesman Problem for Cubic Graphs.
Proceedings of the Algorithms and Data Structures, 8th International Workshop, 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

Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way.
Proceedings of the Graph Drawing, 11th International Symposium, 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.
Discrete & Computational Geometry, 2002

Separating Thickness from Geometric Thickness
CoRR, 2002

Dynamic Generators of Topologically Embedded Graphs
CoRR, 2002

Algorithms for Media
CoRR, 2002

A steady state model for graph power laws
CoRR, 2002

Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way
CoRR, 2002

Optimized Color Gamuts for Tiled Displays
CoRR, 2002

Moebius-Invariant Natural Neighbor Interpolation
CoRR, 2002

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

Algorithms for Coloring Quadtrees.
Algorithmica, 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. Information Theory, 2001

Tangent Spheres and Triangle Centers.
The American Mathematical Monthly, 2001

Separating Geometric Thickness from Book Thickness
CoRR, 2001

The Minimum Expectation Selection Problem
CoRR, 2001

Vertex-Unfoldings of Simplicial Manifolds
CoRR, 2001

Flipping Cubical Meshes
CoRR, 2001

Vertex-Unfoldings of Simplicial Polyhedra
CoRR, 2001

Hinged Kite Mirror Dissection
CoRR, 2001

Optimization Over Zonotopes and Training Support Vector Machines
CoRR, 2001

Optimal Moebius Transformations for Information Visualization and Meshing
CoRR, 2001

Small Maximal Independent Sets and Faster Exact Graph Coloring.
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 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

Fast approximation of centrality.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 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 Journal of Experimental Algorithmics, 2000

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

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

Regression Depth and Center Points.
Discrete & Computational Geometry, 2000

One-Dimensional Peg Solitaire, and Duotaire
CoRR, 2000

One-Dimensional Peg Solitaire
CoRR, 2000

Small Maximal Independent Sets and Faster Exact Graph Coloring
CoRR, 2000

Improved Algorithms for 3-Coloring, 3-Edge-Coloring, and Constraint Satisfaction
CoRR, 2000

Fast Approximation of Centrality
CoRR, 2000

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

Internet Packet Filter Management and Rectangle Geometry
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

Multivariate regression depth.
Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

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

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

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

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

Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions.
Discrete & Computational Geometry, 1999

Geometric Thickness of Complete Graphs
CoRR, 1999

Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs
CoRR, 1999

Subgraph Isomorphism in Planar Graphs and Related Problems
CoRR, 1999

Setting Parameters by Example
CoRR, 1999

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

Multivariate Regression Depth
CoRR, 1999

Emerging Challenges in Computational Topology
CoRR, 1999

Quadrilateral Meshing by Circle Packing
CoRR, 1999

Ununfoldable Polyhedra with Convex Faces
CoRR, 1999

Beta-Skeletons have Unbounded Dilation
CoRR, 1999

Algorithms for Coloring Quadtrees
CoRR, 1999

Hinged Dissection of Polyominoes and Polyforms
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

Incremental and Decremental Maintenance of Planar Width.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Setting Parameters by Example.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 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

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.
Discrete & Computational Geometry, 1998

The Crust and the beta-Skeleton: Combinatorial Curve Reconstruction.
Graphical Models and Image Processing, 1998

Linear Complexity Hexahedral Mesh Generation
CoRR, 1998

Optimal Point Placement for Mesh Smoothing
CoRR, 1998

Incremental and Decremental Maintenance of Planar Width
CoRR, 1998

Regression Depth and Center Points
CoRR, 1998

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

Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Geometric Thickness of Complete Graphs.
Proceedings of the Graph Drawing, 6th International Symposium, 1998

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

Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions.
Proceedings of the Fourteenth Annual Symposium on Computational Geometry, 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. Geometry Appl., 1997

On Nearest-Neighbor Graphs.
Discrete & Computational Geometry, 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

Optimal Point Placement for Mesh Smoothing.
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. Geometry Appl., 1996

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

Using Sparsification for Parametric Minimum Spanning Tree Problems.
Proceedings of the Algorithm Theory, 1996

Linear Complexity Hexahedral Mesh Generation.
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

On Triangulating Three-Dimensional Polygons.
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

1995
Triangulating polygons without large angles.
Int. J. Comput. Geometry 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.
Discrete & Computational Geometry, 1995

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

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

Geometric lower bounds for parametric matroid optimization.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Subgraph Isomorphism in Planar Graphs and Related Problems.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

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

3-Coloring in Time O(1.3446n): A No-MIS Algorithm.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 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. Geometry Appl., 1994

Iterated Nearest Neighbors and Finding Minimal Polytopes.
Discrete & Computational Geometry, 1994

Approximating the Minimum Weight Steiner Triangulation.
Discrete & Computational Geometry, 1994

On the Number of Minimal 1-Steiner Trees.
Discrete & Computational Geometry, 1994

Visibility with a Moving Point of View.
Algorithmica, 1994

Clustering for Faster Network Simplex Pivots.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Average Case Analysis of Dynamic Geometric Optimization.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Finding the k Shortest Paths
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 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.
Discrete & Computational Geometry, 1993

Parallel Construction of Quadtrees and Quality Triangulations.
Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

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

Iterated Nearest Neighbors and Finding Minimal Polytopes.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

A Deterministic Linear Time Algorithm for Geometric Separators and its Applications.
Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 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.
Mathematical Systems 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 Journal on Computing, 1992

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

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

Finding Minimum Area k-gons.
Discrete & Computational Geometry, 1992

Finding the k Smallest Spanning Trees.
BIT, 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

Triangulating Polygons without Large Angles.
Proceedings of the Eighth Annual Symposium on Computational Geometry, 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. Geometry Appl., 1991

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

Offline Algorithms for Dynamic Minimum Spanning Tree Problems.
Proceedings of the Algorithms and Data Structures, 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

The Expected Extremes in a Delaunay Triangulation.
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Dynamic Three-Dimensional Linear Programming
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Polynomial-Size Nonobtuse Triangulation of Polygons.
Proceedings of the Seventh Annual Symposium on Computational Geometry, 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.
Discrete Mathematics, 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

Visibility with a Moving Point of View.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

Provably Good Mesh Generation
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 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...