[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Finding Geometric Representations of Apex Graphs is NP-Hard

  • Conference paper
  • First Online:
WALCOM: Algorithms and Computation (WALCOM 2022)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 13174))

Included in the following conference series:

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].

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 64.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 84.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    For a set of geometric objects \(\mathscr {C}\), its intersection graph, \(I(\mathscr {C})\), has \(\mathscr {C}\) as the vertex set and two vertices are adjacent if and only if the corresponding geometric objects intersect.

  2. 2.

    Formally, two closed disks are said to touch each other if they share exactly one point.

  3. 3.

    Formally, a simple curve is a subset of the plane which is homeomorphic to the interval [0, 1].

References

  1. Agarwal, P.K., Van Kreveld, M.J.: Label placement by maximum independent set in rectangles. Comput. Geom. 11(3–4), 209–218 (1998)

    Article  MathSciNet  Google Scholar 

  2. Andreev, E.M.: On convex polyhedra in Lobacevskii spaces. Math. USSR-Sbornik 10(3), 413 (1970)

    Article  Google Scholar 

  3. Auer, C., Gleißner, A.: Characterizations of deque and queue graphs. In: Kolman, P., Kratochvíl, J. (eds.) WG 2011. LNCS, vol. 6986, pp. 35–46. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25870-1_5

    Chapter  Google Scholar 

  4. Benzer, S.: On the topology of the genetic fine structure. Proc. Natl. Acad. Sci. U.S.A. 45(11), 1607 (1959)

    Article  Google Scholar 

  5. Bernhart, F., Kainen, P.C.: The book thickness of a graph. J. Comb. Theory Ser. B 27(3), 320–331 (1979)

    Article  MathSciNet  Google Scholar 

  6. Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335–379 (1976)

    Article  MathSciNet  Google Scholar 

  7. Bowen, C., Durocher, S., Löffler, M., Rounds, A., Schulz, A., Tóth, C.D.: Realization of simply connected polygonal linkages and recognition of unit disk contact trees. In: Di Giacomo, E., Lubiw, A. (eds.) GD 2015. LNCS, vol. 9411, pp. 447–459. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-27261-0_37

    Chapter  MATH  Google Scholar 

  8. Breu, H., Kirkpatrick, D.G.: Unit disk graph recognition is NP-hard. Comput. Geom. 9(1–2), 3–24 (1998)

    Article  MathSciNet  Google Scholar 

  9. Chalopin, J., Gonçalves, D.: Every planar graph is the intersection graph of segments in the plane. In: STOC, pp. 631–638 (2009)

    Google Scholar 

  10. Chalopin, J., Gonçalves, D., Ochem, P.: Planar graphs have 1-string representations. Discrete Comput. Geom. 43(3), 626–647 (2010)

    Article  MathSciNet  Google Scholar 

  11. Chaplick, S., Jelínek, V., Kratochvíl, J., Vyskočil, T.: Bend-bounded path intersection graphs: sausages, noodles, and waffles on a grill. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds.) WG 2012. LNCS, vol. 7551, pp. 274–285. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34611-8_28

    Chapter  Google Scholar 

  12. Chmel, P.: Algorithmic aspects of intersection representations. Bachelor’s thesis (2020)

    Google Scholar 

  13. Chung, F., Leighton, F.T., Rosenberg, A.: Diogenes: a methodology for designing fault-tolerant VLSI processor arrays. Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Microsystems Program Office (1983)

    Google Scholar 

  14. Chung, F.R.K., Leighton, F.T., Rosenberg, A.L.: A graph layout problem with applications to VLSI design (1984)

    Google Scholar 

  15. de Castro, N., Cobos, F.J., Dana, J.C., Márquez, A., Noy, M.: Triangle-free planar graphs as segments intersection graphs. In: Kratochvíyl, J. (ed.) GD 1999. LNCS, vol. 1731, pp. 341–350. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-46648-7_35

    Chapter  Google Scholar 

  16. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (2012). https://doi.org/10.1007/978-1-4612-0515-9

  17. Gao, J., Guibas, L.J., Hershberger, J., Zhang, L., Zhu, A.: Geometric spanners for routing in mobile networks. IEEE J. Sel. Areas Commun. 23(1), 174–185 (2005)

    Article  Google Scholar 

  18. Ga̧sieniec, L., Klasing, R., Radzik, T.: IWOCA 2020, vol. 12126. Springer, Cham (2020)

    Google Scholar 

  19. Gonçalves, D.: 3-colorable planar graphs have an intersection segment representation using 3 slopes. In: Sau, I., Thilikos, D.M. (eds.) WG 2019. LNCS, vol. 11789, pp. 351–363. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30786-8_27

    Chapter  Google Scholar 

  20. Gonçalves, D.: Not all planar graphs are in PURE-4-DIR. J. Graph Algorithms Appl. 24(3), 293–301 (2020)

    Article  MathSciNet  Google Scholar 

  21. Gonçalves, D., Isenmann, L., Pennarun, C.: Planar graphs as L-intersection or L-contact graphs. In: SODA, pp. 172–184. SIAM (2018)

    Google Scholar 

  22. Gonçalves, D., Lévêque, B., Pinlou, A.: Homothetic triangle representations of planar graphs. J. Graph Algorithms Appl. 23(4), 745–753 (2019)

    Article  MathSciNet  Google Scholar 

  23. Gupta, A., Impagliazzo, R.: Computing planar intertwines. In: FOCS, pp. 802–811. Citeseer (1991)

    Google Scholar 

  24. Hartman, I.B., Newman, I., Ziv, R.: On grid intersection graphs. Discret. Math. 87(1), 41–52 (1991)

    Article  MathSciNet  Google Scholar 

  25. Klemz, B., Nöllenburg, M., Prutkin, R.: Recognizing weighted disk contact graphs. In: Di Giacomo, E., Lubiw, A. (eds.) GD 2015. LNCS, vol. 9411, pp. 433–446. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-27261-0_36

    Chapter  Google Scholar 

  26. Koebe, P.: Kontaktprobleme der konformen Abbildung. Hirzel (1936)

    Google Scholar 

  27. Kratochvíl, J.: String graphs. II. Recognizing string graphs is NP-hard. J. Comb. Theory Series B 52(1), 67–78 (1991)

    Article  MathSciNet  Google Scholar 

  28. Kratochvíl, J.: A special planar satisfiability problem and a consequence of its NP-completeness. Discret. Appl. Math. 52(3), 233–252 (1994)

    Article  MathSciNet  Google Scholar 

  29. Kratochvíl, J., Matoušek, J.: NP-hardness results for intersection graphs. Comment. Math. Univ. Carol. 30(4), 761–773 (1989)

    MathSciNet  MATH  Google Scholar 

  30. Kratochvíl, J., Matousek, J.: Intersection graphs of segments. J. Comb. Theory Ser. B 62(2), 289–315 (1994)

    Article  MathSciNet  Google Scholar 

  31. Kratochvíl, J., Pergel, M.: Geometric intersection graphs: do short cycles help? In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, pp. 118–128. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73545-8_14

    Chapter  Google Scholar 

  32. Kuhn, F., Wattenhofer, R., Zollinger, A.: Ad hoc networks beyond unit disk graphs. Wireless Netw. 14(5), 715–729 (2008)

    Article  Google Scholar 

  33. Li, X.-Y.: Algorithmic, geometric and graphs issues in wireless networks. Wirel. Commun. Mob. Comput. 3(2), 119–140 (2003)

    Article  Google Scholar 

  34. Mustaţă, I., Pergel, M.: On unit grid intersection graphs and several other intersection graph classes. Acta Math. Univ. Comenian. 88(3), 967–972 (2019)

    MathSciNet  Google Scholar 

  35. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. OUP, Oxford (2006)

    Google Scholar 

  36. Pach, J.: Why are string graphs so beautiful? In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 1–1. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11805-0_1

    Chapter  Google Scholar 

  37. Rajaraman, R.: Topology control and routing in ad hoc networks: a survey. ACM SIGACT News 33(2), 60–73 (2002)

    Article  Google Scholar 

  38. Robertson, N., Seymour, P.D.: Graph minors XX Wagner’s conjecture. J. Comb. Theory Ser. B 92(2), 325–357 (2004)

    Article  MathSciNet  Google Scholar 

  39. Schaefer, M., Sedgwick, E., Štefankovič, D.: Recognizing string graphs in NP. J. Comput. Syst. Sci. 67(2), 365–380 (2003)

    Article  MathSciNet  Google Scholar 

  40. Scheinerman, E.R.: Intersection Classes and Multiple Intersection Parameters of Graphs. Princeton University (1984)

    Google Scholar 

  41. Sherwani, N.A.: Algorithms for VLSI Physical Design Automation. Springer, New York (2007)

    MATH  Google Scholar 

  42. Sinden, F.W.: Topology of thin film RC circuits. Bell Syst. Tech. J. 45(9), 1639–1662 (1966)

    Article  Google Scholar 

  43. Thilikos, D.M., Bodlaender, H.L.: Fast partitioning l-apex graphs with applications to approximating maximum induced-subgraph problems. Inf. Process. Lett. 61(5), 227–232 (1997)

    Article  MathSciNet  Google Scholar 

  44. Thomassen, C.: Interval representations of planar graphs. J. Comb. Theory Ser. B 40(1), 9–20 (1986)

    Article  MathSciNet  Google Scholar 

  45. Thurston, W.: Hyperbolic geometry and 3-manifolds. Low-dimensional topology (Bangor, 1979) 48, 9–25 (1982)

    Google Scholar 

  46. Welsh, D.J.A.: Knots and braids: some algorithmic questions. Contemp. Math. 147 (1993)

    Google Scholar 

  47. Wigderson, A.: The complexity of the Hamiltonian circuit problem for maximal planar graphs. Technical report, EECS 198, Princeton University, USA (1982)

    Google Scholar 

  48. Xu, J., Berger, B.: Fast and accurate algorithms for protein side-chain packing. J. ACM (JACM) 53(4), 533–557 (2006)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This work was done when Kshitij Gajjar was a postdoctoral researcher at Technion, Israel. Kshitij Gajjar’s work is partially supported by NUS ODPRT Grant, WBS No. R-252-000-A94-133. Both authors thank the organisers of Graphmasters 2020 [18] for providing the virtual environment that initiated this research.

Author information

Authors and Affiliations

  1. Univ Lyon, LABEX, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, Lyon, France

    Dibyayan Chakraborty

  2. National University of Singapore, Singapore, Singapore

    Kshitij Gajjar

Authors
  1. Dibyayan Chakraborty
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kshitij Gajjar
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dibyayan Chakraborty .

Editor information

Editors and Affiliations

  1. University of Bonn, Bonn, Germany

    Petra Mutzel

  2. Bangladesh University of Engineering and Technology (BUET), Dhaka, Bangladesh

    Md. Saidur Rahman

  3. Universitas Jember, Jember, Indonesia

    Slamin

Rights and permissions

Reprints and permissions

Copyright information

© 2022 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Chakraborty, D., Gajjar, K. (2022). Finding Geometric Representations of Apex Graphs is NP-Hard. In: Mutzel, P., Rahman, M.S., Slamin (eds) WALCOM: Algorithms and Computation. WALCOM 2022. Lecture Notes in Computer Science(), vol 13174. Springer, Cham. https://doi.org/10.1007/978-3-030-96731-4_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-96731-4_14

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-96730-7

  • Online ISBN: 978-3-030-96731-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation