7 papers
Entropy-Bounded Computational Geometry Made Easier and Sensitive to Sortedness
David Eppstein, Michael T. Goodrich, Abraham M. Illickan +1
We study entropy-bounded computational geometry, that is, geometric algorithms whose running times depend on a given measure of the input entropy. Specifically, we introduce a meas…
Fast Geographic Routing in Fixed-Growth Graphs
Ofek Gila, Michael T. Goodrich, Abraham M. Illickan +1
In the 1960s, the social scientist Stanley Milgram performed his famous "small-world" experiments where he found that people in the US who are far apart geographically are neverthe…
Maximal Independent Sets in Planar Triangulations
P. Francis, Abraham M. Illickan, Lijo M. Jose +1
We show that every planar triangulation on vertices has a maximal independent set of size at most . This affirms a conjecture by Botler, Fernandes and Gutiérrez [Electron.…
Drawing Planar Graphs and 1-Planar Graphs Using Cubic Bézier Curves with Bounded Curvature
David Eppstein, Michael T. Goodrich, Abraham M. Illickan
We study algorithms for drawing planar graphs and 1-planar graphs using cubic Bézier curves with bounded curvature. We show that any n-vertex 1-planar graph has a 1-planar RAC draw…
Krenn-Gu conjecture for sparse graphs
L. Sunil Chandran, Rishikesh Gajjala, Abraham M. Illickan
Greenberger-Horne-Zeilinger (GHZ) states are quantum states involving at least three entangled particles. They are of fundamental interest in quantum information theory, and the co…
Face-hitting Dominating Sets in Planar Graphs
P. Francis, Abraham M. Illickan, Lijo M. Jose +1
A dominating set of a graph is a subset of its vertices such that each vertex of not in has a neighbor in . A face-hitting set of a plane graph is a set …
Disjoint Total Dominating Sets in Near-Triangulations
P. Francis, Abraham M. Illickan, Lijo M. Jose +1
We show that every simple planar near-triangulation with minimum degree at least three contains two disjoint total dominating sets. The class includes all simple planar triangulati…