Finding Geometric Representations of Apex Graphs is NP-Hard

Planar graphs can be represented as intersection graphs of different types of geometric objects in the plane, e.g., circles (Koebe, 1936), line segments (Chalopin \& Gon{\c{c}}alves, 2009), \textsc{L}-shapes (Gon{\c{c}}alves~et al., 2018). Furthermore, these representations can be obtained in polynomial time when the planar graph is provided as input. For general graphs, however, even deciding whether such representations exist is often NP-hard. We consider apex graphs, i.e., graphs that can be made planar by removing one vertex from them. More precisely, we show that recognizing every graph class $\mathcal{G}$ which satisfies \textsc{Pure-2-Dir} $\subseteq \mathcal{G} \subseteq$ \textsc{1-String} is NP-hard, even when the input graphs are apex graphs. Here, \textsc{Pure-2-Dir} is the class of intersection graphs of axis-parallel line segments (where intersections are allowed only between horizontal and vertical segments) and \textsc{1-String} is the class of intersection graphs of simple curves (where two curves share at most one point) in the plane. Most of the known NP-hardness reductions for these problems are from variants of 3-SAT. We reduce from \textsc{Planar Hamiltonian Path Completion}, which uses the more intuitive notion of planarity. As a result, our proof is much simpler and encapsulates several classes of geometric graphs.