- Convex-arc drawings of pseudolines.
D. Eppstein,
M. van Garderen,
B. Speckmann, and
T. Ueckerdt.
21st Int. Symp. Graph Drawing (poster), Bordeaux, France, 2013.
Springer, Lecture Notes in Comp. Sci. 8242, 2013, pp. 522–523.
arXiv:1601.06865.
We show that every outerplanar weak pseudoline arrangement (a collection
of curves topologically equivalent to lines, each crossing at most once
but possibly zero times, with all crossings belonging to an infinite
face) can be straightened to a hyperbolic line arrangement. As a
consequence such an arrangement can also be drawn in the Euclidean plane
with each pseudoline represented as a convex piecewise-linear curve with
at most two bends. In contrast, for arbitrary pseudoline arrangements, a
linear number of bends is sufficient and sometimes necessary.
- Geodesic paths passing through all faces on a polyhedron.
E. Demaine,
M. Demaine,
D. Eppstein,
H. Ito,
Y. Katayama,
W. Maruyama, and
Y. Uno.
24th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, 2022, pp. 58–59.
Which convex polyhedra have the property that there exist two points on
the surface of the polyhedron whose shortest path passes through all of
the faces of the polyhedron? The answer is yes for the tetrahedron, and
for certain prisms, but no for all other regular polyhedra.
- On the complexity of embedding in graph products.
T. Biedl,
D. Eppstein, and
T. Ueckerdt.
arXiv:2303.17028.
Proc. 35th Canadian Conference on Computational Geometry, 2023, pp. 77–88.
Row treewidth (embedding a graph as a subgraph of a strong product of a
path with a low treewidth graph), row pathwidth, and row tree-depth are
all NP-hard.
- Computational complexities of folding.
D. Eppstein.
Invited talk,
8th International Meeting on Origami in Science, Mathematics and
Education, Melbourne, Australia, 2024.
Invited talk, 26th Japan Conference
on Discrete and Computational Geometry, Graphs, and Games, Tokyo, 2024.
arXiv:2410.07666.
- Noncrossing longest paths and cycles.
G. Aloupis,
A. Biniaz,
P. Bose,
J.-L. De Carufel,
D. Eppstein,
A. Maheshwari,
S. Odak,
M. Smid,
C. Tóth, and
P. Valtr.
32nd International Symposium on Graph Drawing and Network
Visualization.
Leibniz
International Proceedings in Informatics (LIPIcs) 320, 2024,
pp. 36:1–36:17.
arXiv:2410.05580.