Header menu link for other important links
X
Finding Geometric Representations of Apex Graphs is NP-Hard
D. Chakraborty,
Published in Springer Science and Business Media Deutschland GmbH
2022
Volume: 13174 LNCS
   
Pages: 161 - 174
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 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 g, recognizing every graph class G such that PURE-2-DIR⊆G⊆1-STRING is NP -hard, even if the inputs are apex graphs of girth at least g. 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 1-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 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. © 2022, Springer Nature Switzerland AG.
About the journal
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Science and Business Media Deutschland GmbH
ISSN03029743