Finding Geometric Representations of Apex Graphs is NP-Hard

Abstract

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çalves, SODA 2009), L-shapes (Gonçalves et al., SODA 2018). For general graphs, however, even deciding whether such representations exist is often $\mathsf{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 $\mathsf{NP}$-hard.

More precisely, we show that for every positive integer g, recognizing every graph class $\mathscr {G}$ such that ${\textsc {Pure}}\text {-}{\textsc {2}}\text {-}{\textsc {Dir}}\subseteq \mathscr {G}\subseteq {\textsc {1}}\text {-}{\textsc {String}}$ is $\mathsf{NP}$-hard, even if the inputs are apex graphs of girth at least g. Here, ${\textsc {Pure}}\text {-}{\textsc {2}}\text {-}{\textsc {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}}\text {-}{\textsc {String}}$ is the class of intersection graphs of simple curves (where two curves cross at most once) in the plane. This partially answers an open question raised by Kratochvíl & Pergel (COCOON, 2007).

Most known $\textsf {NP}$-hardness reductions for these problems are from variants of 3-SAT. We reduce from the Planar Hamiltonian Path Completion problem, which uses the more intuitive notion of planarity. As a result, our proof is much simpler and encapsulates several classes of geometric graphs.

D. Chakraborty—This work was done when the author was a postdoctoral fellow at the Indian Institute of Science, Bangalore.

K. Gajjar—This project has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No. 682203-ERC-[Inf-Speed-Tradeoff].