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), $\text{textsc}L$-shapes (Gon{\c{c}}alves et al, 2018). 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. We show, somewhat surprisingly, that deciding whether geometric representations exist for apex graphs is $NP$-hard. More precisely, we show that for every positive integer $k$, recognizing every graph class $\mathcal{G}$ which satisfies $$\text{textsc}PURE-2-DIR$ \subseteq $\mathcal{G}$ \subseteq $\text{textsc}1-STRING$$is$NP$-hard, even when the input graphs are apex graphs of girth at least $k$. Here, $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 $\text{textsc}1-STRING$ is the class of intersection graphs of simple curves (where two curves share at most one point) in the plane. This partially answers an open question raised by Kratochv{'\i}l & Pergel (2007). Most known $NP$-hardness reductions for these problems are from variants of 3-SAT. We reduce from the $\text{textsc}PLANARHAMILTONIANPATHCOMPLETION$ problem, which uses the more intuitive notion of planarity. As a result, our proof is much simpler and encapsulates several classes of geometric graphs.