default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDDavid Eppstein
David Arthur Eppstein
Person information
- affiliation: University of California, Irvine, Computer Science Department
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j200]David Eppstein:
Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time. Algorithmica 86(9): 3027-3053 (2024)- [j199]David Eppstein, Robert Hickingbotham
, Laura Merker, Sergey Norin, Michal T. Seweryn, David R. Wood:
Three-Dimensional Graph Products with Unbounded Stack-Number. Discret. Comput. Geom. 71(4): 1210-1237 (2024) - [j198]David Eppstein:
On the Biplanarity of Blowups. J. Graph Algorithms Appl. 28(2): 83-99 (2024) - [j197]Marc Distel, Vida Dujmovic, David Eppstein, Robert Hickingbotham, Gwenaël Joret, Piotr Micek, Pat Morin, Michal T. Seweryn, David R. Wood:
Product Structure Extension of the Alon-Seymour-Thomas Theorem. SIAM J. Discret. Math. 38(3): 2095-2107 (2024) - [c244]Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Saeed Odak, Michiel Smid, Csaba D. Tóth, Pavel Valtr:
Noncrossing Longest Paths and Cycles. GD 2024: 36:1-36:17 - [c243]David Eppstein, Michael T. Goodrich, Abraham M. Illickan:
Drawing Planar Graphs and 1-Planar Graphs Using Cubic Bézier Curves with Bounded Curvature. GD 2024: 39:1-39:17 - [i237]David Eppstein:
Non-Euclidean Erdős-Anning Theorems. CoRR abs/2401.06328 (2024) - [i236]Hadi Khodabandeh, David Eppstein:
Maintaining Light Spanners via Minimal Updates. CoRR abs/2403.03290 (2024) - [i235]Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Saeed Odak, Michiel Smid, Csaba D. Tóth, Pavel Valtr:
Noncrossing Longest Paths and Cycles. CoRR abs/2410.05580 (2024) - [i234]David Eppstein:
Computational Complexities of Folding. CoRR abs/2410.07666 (2024) - [i233]David Eppstein, Michael T. Goodrich, Abraham M. Illickan:
Drawing Planar Graphs and 1-Planar Graphs Using Cubic Bézier Curves with Bounded Curvature. CoRR abs/2410.12083 (2024) - 2023
- [j196]David Eppstein:
A Stronger Lower Bound on Parametric Minimum Spanning Trees. Algorithmica 85(6): 1738-1753 (2023) - [j195]David Eppstein:
Locked and Unlocked Smooth Embeddings of Surfaces. Comput. Geom. Topol. 2(2): 5:1-5:20 (2023) - [j194]Oswin Aichholzer, David Eppstein, Eva-Maria Hainzl:
Geometric dominating sets - a minimum version of the No-Three-In-Line Problem. Comput. Geom. 108: 101913 (2023) - [j193]David Eppstein, Daniel Frishberg, Martha C. Osegueda:
Angles of arc-polygons and Lombardi drawings of cacti. Comput. Geom. 112: 101982 (2023) - [j192]David Eppstein, Andrea Lincoln, Virginia Vassilevska Williams:
Quasipolynomiality of the Smallest Missing Induced Subgraph. J. Graph Algorithms Appl. 27(5): 329-339 (2023) - [j191]David Eppstein:
The Complexity of Iterated Reversible Computation. TheoretiCS 2 (2023) - [c242]David Eppstein:
A Parameterized Algorithm for Flat Folding. CCCG 2023: 35-42 - [c241]Therese Biedl, David Eppstein, Torsten Ueckerdt:
On the complexity of embedding in graph products. CCCG 2023: 77-88 - [c240]David Eppstein, Rose McCarty:
Geometric Graphs with Unbounded Flip-Width. CCCG 2023: 197-206 - [c239]David Eppstein:
Non-Crossing Hamiltonian Paths and Cycles in Output-Polynomial Time. SoCG 2023: 29:1-29:16 - [c238]David Eppstein:
On the Biplanarity of Blowups. GD (1) 2023: 3-17 - [c237]Alvin Chiu, David Eppstein, Michael T. Goodrich:
Manipulating Weights to Improve Stress-Graph Drawings of 3-Connected Planar Graphs. GD (2) 2023: 141-149 - [c236]David Eppstein, Daniel Frishberg:
Improved Mixing for the Convex Polygon Triangulation Flip Walk. ICALP 2023: 56:1-56:17 - [c235]David Eppstein, Daniel Frishberg:
Rapid Mixing for the Hardcore Glauber Dynamics and Other Markov Chains in Bounded-Treewidth Graphs. ISAAC 2023: 30:1-30:13 - [c234]David Eppstein:
Lower Bounds for Non-adaptive Shortest Path Relaxation. WADS 2023: 416-429 - [i232]David Eppstein:
Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time. CoRR abs/2303.00147 (2023) - [i231]Therese Biedl, David Eppstein, Torsten Ueckerdt:
On the complexity of embedding in graph products. CoRR abs/2303.17028 (2023) - [i230]David Eppstein:
Lower Bounds for Non-Adaptive Shortest Path Relaxation. CoRR abs/2305.09230 (2023) - [i229]David Eppstein, Andrea Lincoln, Virginia Vassilevska Williams:
Quasipolynomiality of the Smallest Missing Induced Subgraph. CoRR abs/2306.11185 (2023) - [i228]David Eppstein:
A Parameterized Algorithm for Flat Folding. CoRR abs/2306.11939 (2023) - [i227]David Eppstein, Rose McCarty:
Geometric Graphs with Unbounded Flip-Width. CoRR abs/2306.12611 (2023) - [i226]Alvin Chiu, David Eppstein, Michael T. Goodrich:
Manipulating Weights to Improve Stress-Graph Drawings of 3-Connected Planar Graphs. CoRR abs/2307.10527 (2023) - 2022
- [j190]Vida Dujmovic, David Eppstein, Robert Hickingbotham, Pat Morin, David R. Wood:
Stack-Number is Not Bounded by Queue-Number. Comb. 42(2): 151-164 (2022) - [j189]Hugo A. Akitaya, Erik D. Demaine, David Eppstein, Tomohiro Tachi, Ryuhei Uehara:
Ununfoldable polyhedra with 6 vertices or 6 faces. Comput. Geom. 103: 101857 (2022) - [j188]David Eppstein, Daniel Frishberg, William Maxwell:
On the treewidth of Hanoi graphs. Theor. Comput. Sci. 906: 1-17 (2022) - [c233]David Eppstein:
Reflections in an Octagonal Mirror Maze. CCCG 2022: 129-134 - [c232]David Eppstein:
Locked and Unlocked Smooth Embeddings of Surfaces. CCCG 2022: 135-142 - [c231]David Eppstein:
Orthogonal Dissection into Few Rectangles. CCCG 2022: 143-150 - [c230]David Eppstein:
Finding Relevant Points for Nearest-Neighbor Classification. SOSA 2022: 68-78 - [c229]David Eppstein, Hadi Khodabandeh:
Brief Announcement: Distributed Lightweight Spanner Construction for Unit Ball Graphs in Doubling Metrics. SPAA 2022: 57-59 - [c228]David Eppstein, Hadi Khodabandeh:
Distributed Construction of Lightweight Spanners for Unit Ball Graphs. DISC 2022: 21:1-21:23 - [i225]David Eppstein, Robert Hickingbotham, Laura Merker, Sergey Norin, Michal T. Seweryn, David R. Wood:
Three-dimensional graph products with unbounded stack-number. CoRR abs/2202.05327 (2022) - [i224]Oswin Aichholzer, David Eppstein, Eva-Maria Hainzl:
Geometric Dominating Sets. CoRR abs/2203.13170 (2022) - [i223]David Eppstein:
Orthogonal dissection into few rectangles. CoRR abs/2206.10675 (2022) - [i222]David Eppstein:
Reflections in an octagonal mirror maze. CoRR abs/2206.11413 (2022) - [i221]David Eppstein:
Locked and unlocked smooth embeddings of surfaces. CoRR abs/2206.12989 (2022) - [i220]David Eppstein, Daniel Frishberg:
Improved mixing for the convex polygon triangulation flip walk. CoRR abs/2207.09972 (2022) - 2021
- [j187]Giordano Da Lozzo, David Eppstein, Michael T. Goodrich, Siddharth Gupta:
C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width. Algorithmica 83(8): 2471-2502 (2021) - [j186]David Eppstein:
On Polyhedral Realization with Isosceles Triangles. Graphs Comb. 37(4): 1247-1269 (2021) - [j185]David Eppstein:
Bipartite and Series-Parallel Graphs Without Planar Lombardi Drawings. J. Graph Algorithms Appl. 25(1): 549-562 (2021) - [j184]David Eppstein:
Cubic planar graphs that cannot be drawn on few lines. J. Comput. Geom. 12(1): 178-197 (2021) - [j183]David Eppstein, Vijay V. Vazirani:
NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs. SIAM J. Comput. 50(3): 1014-1033 (2021) - [c227]David Eppstein, Daniel Frishberg, Martha C. Osegueda:
Angles of Arc-Polygons and Lombardi Drawings of Cacti. CCCG 2021: 56-64 - [c226]David Eppstein, Hadi Khodabandeh:
On the Edge Crossings of the Greedy Spanner. SoCG 2021: 33:1-33:17 - [c225]David Eppstein, Siddharth Gupta, Elham Havvaei:
Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes. FCT 2021: 217-229 - [c224]David Eppstein, Daniel Frishberg, William Maxwell:
On the Treewidth of Hanoi Graphs. FUN 2021: 13:1-13:21 - [c223]David Eppstein:
Limitations on Realistic Hyperbolic Graph Drawing. GD 2021: 343-357 - [c222]David Eppstein:
A Stronger Lower Bound on Parametric Minimum Spanning Trees. WADS 2021: 343-356 - [c221]David Eppstein:
The Graphs of Stably Matchable Pairs. WG 2021: 349-360 - [i219]David Eppstein, Siddharth Gupta, Elham Havvaei:
Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes. CoRR abs/2101.09918 (2021) - [i218]David Eppstein:
A Stronger Lower Bound on Parametric Minimum Spanning Trees. CoRR abs/2105.05371 (2021) - [i217]David Eppstein, Hadi Khodabandeh:
Optimal Spanners for Unit Ball Graphs in Doubling Metrics. CoRR abs/2106.15234 (2021) - [i216]David Eppstein, Daniel Frishberg, Martha C. Osegueda:
Angles of Arc-Polygons and Lombardi Drawings of Cacti. CoRR abs/2107.03615 (2021) - [i215]David Eppstein:
Limitations on Realistic Hyperbolic Graph Drawing. CoRR abs/2108.07441 (2021) - [i214]David Eppstein:
Finding Relevant Points for Nearest-Neighbor Classification. CoRR abs/2110.06163 (2021) - [i213]David Eppstein, Daniel Frishberg:
Rapid mixing of the hardcore Glauber dynamics and other Markov chains in bounded-treewidth graphs. CoRR abs/2111.03898 (2021) - [i212]David Eppstein:
The Complexity of Iterated Reversible Computation. CoRR abs/2112.11607 (2021) - 2020
- [j182]David Eppstein, Elham Havvaei:
Parameterized Leaf Power Recognition via Embedding into Graph Products. Algorithmica 82(8): 2337-2359 (2020) - [j181]Molly Baird, Sara C. Billey, Erik D. Demaine, Martin L. Demaine, David Eppstein, Sándor P. Fekete, Graham Gordon, Sean Griffin, Joseph S. B. Mitchell, Joshua P. Swanson:
Existence and Hardness of Conveyor Belts. Electron. J. Comb. 27(4): 4 (2020) - [j180]David Eppstein:
Treetopes and Their Graphs. Discret. Comput. Geom. 64(2): 259-289 (2020) - [j179]David Eppstein:
Counting Polygon Triangulations is Hard. Discret. Comput. Geom. 64(4): 1210-1234 (2020) - [j178]David Eppstein, Sariel Har-Peled, Gabriel Nivasch:
Grid Peeling and the Affine Curve-Shortening Flow. Exp. Math. 29(3): 306-316 (2020) - [j177]Gill Barequet, David Eppstein, Michael T. Goodrich, Nil Mamano:
Stable-matching Voronoi diagrams: Combinatorial complexity and algorithms. J. Comput. Geom. 11(1): 26-59 (2020) - [j176]Hugo A. Akitaya, Vida Dujmovic, David Eppstein, Thomas C. Hull, Kshitij Jain, Anna Lubiw:
Face flips in origami tessellations. J. Comput. Geom. 11(1): 397-417 (2020) - [j175]David Eppstein, Sariel Har-Peled, Anastasios Sidiropoulos:
Approximate greedy clustering and distance selection for graph metrics. J. Comput. Geom. 11(1): 629-652 (2020) - [j174]Vida Dujmovic, David Eppstein, Gwenaël Joret, Pat Morin, David R. Wood:
Minor-Closed Graph Classes with Bounded Layered Pathwidth. SIAM J. Discret. Math. 34(3): 1693-1709 (2020) - [j173]Jean Cardinal, Erik D. Demaine, David Eppstein, Robert A. Hearn, Andrew Winslow:
Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect. Theor. Comput. Sci. 806: 332-343 (2020) - [c220]Man-Kwun Chiu, Erik D. Demaine, Yevhenii Diomidov, David Eppstein, Robert A. Hearn, Adam Hesterberg, Matias Korman, Irene Parada, Mikhail Rudoy:
New Results in Sona Drawing: Hardness and TSP Separation. CCCG 2020: 63-72 - [c219]Erik D. Demaine, Martin L. Demaine, David Eppstein, Joseph O'Rourke:
Some Polycubes Have No Edge Zipper Unfolding. CCCG 2020: 101-105 - [c218]Erik D. Demaine, Martin L. Demaine, David Eppstein:
Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra. CCCG 2020: 106-113 - [c217]David Eppstein:
Dynamic Products of Ranks. CCCG 2020: 199-205 - [c216]Glencora Borradaile, Erin Wolf Chambers, David Eppstein, William Maxwell, Amir Nayyeri:
Low-Stretch Spanning Trees of Graphs with Bounded Width. SWAT 2020: 15:1-15:19 - [c215]David Eppstein, Daniel Frishberg, Elham Havvaei:
Simplifying Activity-On-Edge Graphs. SWAT 2020: 24:1-24:14 - [i211]David Eppstein, Daniel Frishberg, Elham Havvaei:
Simplifying Activity-on-Edge Graphs. CoRR abs/2002.01610 (2020) - [i210]David Eppstein, Hadi Khodabandeh:
On the Edge Crossings of the Greedy Spanner. CoRR abs/2002.05854 (2020) - [i209]Glencora Borradaile, Erin Wolf Chambers, David Eppstein, William Maxwell, Amir Nayyeri:
Low-stretch spanning trees of graphs with bounded width. CoRR abs/2004.08375 (2020) - [i208]David Eppstein, Daniel Frishberg, William Maxwell:
On the treewidth of Hanoi graphs. CoRR abs/2005.00179 (2020) - [i207]David Eppstein:
Dynamic Products of Ranks. CoRR abs/2007.08123 (2020) - [i206]Erik D. Demaine, Martin L. Demaine, David Eppstein:
Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra. CoRR abs/2007.14525 (2020) - [i205]Man-Kwun Chiu, Erik D. Demaine, Yevhenii Diomidov, David Eppstein, Robert A. Hearn, Adam Hesterberg, Matias Korman, Irene Parada, Mikhail Rudoy:
New Results in Sona Drawing: Hardness and TSP Separation. CoRR abs/2007.15784 (2020) - [i204]David Eppstein:
On Polyhedral Realization with Isosceles Triangles. CoRR abs/2009.00116 (2020) - [i203]David Eppstein:
The Graphs of Stably Matchable Pairs. CoRR abs/2010.09230 (2020) - [i202]Vida Dujmovic, David Eppstein, Robert Hickingbotham, Pat Morin, David R. Wood:
Stack-number is not bounded by queue-number. CoRR abs/2011.04195 (2020)
2010 – 2019
- 2019
- [j172]Ahmad Biniaz, Prosenjit Bose, Kimberly Crosbie, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Michiel H. M. Smid:
Maximum Plane Trees in Multipartite Geometric Graphs. Algorithmica 81(4): 1512-1534 (2019) - [j171]Michael J. Bannister, William E. Devanny, Vida Dujmovic, David Eppstein, David R. Wood:
Track Layouts, Layered Path Decompositions, and Leveled Planarity. Algorithmica 81(4): 1561-1583 (2019) - [j170]Mark de Berg, Sergio Cabello, Otfried Cheong, David Eppstein, Christian Knauer:
Covering many points with a small-area box. J. Comput. Geom. 10(1): 207-222 (2019) - [j169]David Eppstein:
Realization and connectivity of the graphs of origami flat foldings. J. Comput. Geom. 10(1): 257-280 (2019) - [c214]David Eppstein:
Bipartite and Series-Parallel Graphs Without Planar Lombardi Drawings. CCCG 2019: 17-22 - [c213]David Eppstein:
Cubic Planar Graphs That Cannot Be Drawn On Few Lines. SoCG 2019: 32:1-32:15 - [c212]David Eppstein:
Counting Polygon Triangulations is Hard. SoCG 2019: 33:1-33:17 - [c211]Therese Biedl, Erin Wolf Chambers, David Eppstein, Arnaud de Mesmay, Tim Ophelders:
Homotopy Height, Grid-Major Height and Graph-Drawing Height. GD 2019: 468-481 - [c210]Nil Mamano, Alon Efrat, David Eppstein, Daniel Frishberg, Michael T. Goodrich, Stephen G. Kobourov, Pedro Matias, Valentin Polishchuk:
New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs. ISAAC 2019: 51:1-51:21 - [c209]David Eppstein, Michael T. Goodrich, James A. Liu, Pedro Matias:
Tracking Paths in Planar Graphs. ISAAC 2019: 54:1-54:17 - [c208]Giordano Da Lozzo, David Eppstein, Michael T. Goodrich, Siddharth Gupta:
C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width. IPEC 2019: 9:1-9:17 - [c207]David Eppstein, Bruce A. Reed:
Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time. SODA 2019: 589-605 - [c206]David Eppstein, Vijay V. Vazirani:
NC Algorithms for Computing a Perfect Matching, the Number of Perfect Matchings, and a Maximum Flow in One-Crossing-Minor-Free Graphs. SPAA 2019: 23-30 - [c205]Erik D. Demaine, David Eppstein, Adam Hesterberg, Kshitij Jain, Anna Lubiw, Ryuhei Uehara, Yushi Uno:
Reconfiguring Undirected Paths. WADS 2019: 353-365 - [i201]Alon Efrat, David Eppstein, Daniel Frishberg, Michael T. Goodrich, Stephen G. Kobourov, Nil Mamano, Pedro Matias, Valentin Polishchuk:
Euclidean TSP, Motorcycle Graphs, and Other New Applications of Nearest-Neighbor Chains. CoRR abs/1902.06875 (2019) - [i200]David Eppstein:
Counting Polygon Triangulations is Hard. CoRR abs/1903.04737 (2019) - [i199]David Eppstein:
Cubic Planar Graphs that cannot be Drawn on few Lines. CoRR abs/1903.05256 (2019) - [i198]Erik D. Demaine, David Eppstein, Adam Hesterberg, Kshitij Jain, Anna Lubiw, Ryuhei Uehara, Yushi Uno:
Reconfiguring Undirected Paths. CoRR abs/1905.00518 (2019) - [i197]David Eppstein:
Bipartite and Series-Parallel Graphs Without Planar Lombardi Drawings. CoRR abs/1906.04401 (2019) - [i196]Erik D. Demaine, Martin L. Demaine, David Eppstein, Joseph O'Rourke:
Some Polycubes Have No Edge-Unzipping. CoRR abs/1907.08433 (2019) - [i195]David Eppstein, Michael T. Goodrich, James A. Liu, Pedro Matias:
Tracking Paths in Planar Graphs. CoRR abs/1908.05445 (2019) - [i194]Therese Biedl, Erin Wolf Chambers, David Eppstein, Arnaud de Mesmay, Tim Ophelders:
Homotopy height, grid-major height and graph-drawing height. CoRR abs/1908.05706 (2019) - [i193]Molly Baird, Sara C. Billey, Erik D. Demaine, Martin L. Demaine, David Eppstein, Sándor P. Fekete, Graham Gordon, Sean Griffin, Joseph S. B. Mitchell, Joshua P. Swanson:
Existence and hardness of conveyor belts. CoRR abs/1908.07668 (2019) - [i192]Giordano Da Lozzo, David Eppstein, Michael T. Goodrich, Siddharth Gupta:
C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width. CoRR abs/1910.02057 (2019) - [i191]Hugo A. Akitaya, Vida Dujmovic, David Eppstein, Thomas C. Hull, Kshitij Jain, Anna Lubiw:
Face flips in origami tessellations. CoRR abs/1910.05667 (2019) - 2018
- [j168]David Eppstein, Philipp Kindermann, Stephen G. Kobourov, Giuseppe Liotta, Anna Lubiw, Aude Maignan, Debajyoti Mondal, Hamideh Vosoughpour, Sue Whitesides, Stephen K. Wismath:
On the Planar Split Thickness of Graphs. Algorithmica 80(3): 977-994 (2018) - [j167]David Eppstein, Daniel S. Hirschberg:
From Discrepancy to Majority. Algorithmica 80(4): 1278-1297 (2018) - [j166]Ahmad Biniaz, Prosenjit Bose, David Eppstein, Anil Maheshwari, Pat Morin, Michiel H. M. Smid:
Spanning Trees in Multipartite Geometric Graphs. Algorithmica 80(11): 3177-3191 (2018) - [j165]Oswin Aichholzer, Michael Biro, Erik D. Demaine, Martin L. Demaine, David Eppstein, Sándor P. Fekete, Adam Hesterberg, Irina Kostitsyna, Christiane Schmidt:
Folding Polyominoes into (Poly)Cubes. Int. J. Comput. Geom. Appl. 28(3): 197-226 (2018) - [j164]