Graphs of intersections of closed polygonal chains

DOI: https://doi.org/10.33581/2520-6508-2021-1-54-68

Abstract

In the paper such subclass of string graphs as intersection graphs of closed polygonal chains (class of CPC-graphs) was considered, necessary conditions for belonging to that class, forbidden subgraphs and operations with graphs which preserve belonging to the CPC class were found. Considered question about the existence of k-regular CPC-graphs, particularly, pairs (k, n), such that there exists k-regular CPC-graph on n vertexes were found, proved that there are infinitely many k-regular CPC-graphs for any k ∈ N, estimations for the number of k, such that k-regular graph on n vertexes exists, were given. Algorithmic questions in the class of CPC-graphs were investigated. It was proved that independent and dominating set problems, coloring problem and the problem about maximal cycle are NP-hard in the class of CPC-graphs, and problem of recognition of the CPC-graphs belongs to the PSPACE class.

Author Biographies

Nikolai P. Prochorov, Belarusian State University, 4 Niezaliežnasci Avenue, Minsk 220030, Belarus

master’s degree student at the department of discrete mathematics and algoritmics, faculty of applied mathematics and computer science

Ekaterina N. Dul, Belarusian State University, 4 Niezaliežnasci Avenue, Minsk 220030, Belarus

student at the faculty of applied mathematics and computer science

References

  1. Sinden FW. Topology of thin film RC circuits. The Bell System Technical Journal. 1966;45(9):1639–1662. DOI: 10.1002/ j.1538-7305.1966.tb01713.x.
  2. Ehrlich G, Even S, Tarjan RE. Intersection graphs of curves in the plane. Journal of Combinatorial Theory. Series B. 1976; 21(1):8–20. DOI: 10.1016/0095-8956(76)90022-8.
  3. Chalopin J, Gonçalves D. Every planar graph is the intersection graph of segments in the plane: extended abstract. In: Proceedings of the Forty-first annual ACM symposium on theory of computing; 2009 May 31 – June 2; Bethesda, Maryland, USA. New York: Association for Computing Machinery; 2009. p. 631–638. DOI: 10.1145/1536414.1536500.
  4. Kratochvíl J, Matoušek J. Intersection graphs of segments. Journal of Combinatorial Theory. Series B. 1994;62(2):289–315. DOI: 10.1006/jctb.1994.1071.
  5. Kratochvíl J. String graphs. II. Recognizing string graphs is NP-hard. Journal of Combinatorial Theory. Series B. 1991;52(1):67–78. DOI: 10.1016/0095-8956(91)90091-W.
  6. Ore O. Graphs and their uses. New York: Random House; 1963. VIII, 131 p. Russian edition: Ore O. Grafy i ikh primenenie. Golovina LI, translator; Yaglom IM, editor. Moscow: Mir; 1965. 174 p.
  7. Kratochvíl J. String graphs. I. The number of critical nonstring graphs is infinite. Journal of Combinatorial Theory. Series B. 1991;52(1):53–66. DOI: 10.1016/0095-8956(91)90090-7.
  8. Dangelmayr C. Intersection graphs of pseudosegments [dissertation]. Berlin: Freien Universität Berlin; 2010. 136 p.
  9. Fuks DB. [Selfintersections of closed polygonal chains]. Kvant. 1988;1:30–34. Russian.
  10. Keil JM. The complexity of domination problems in circle graphs. Discrete Applied Mathematics. 1993;42(1):51–63. DOI: 10.1016/0166-218X(93)90178-Q.
  11. Unger W. On the k-colouring of circle-graphs. In: Cori R, Wirsing M, editors. STACS 88. 5th Annual symposium on theoretical aspects of computer science; 1988 February 11–13; Bordeaux, France. Berlin: Springer-Verlag; 1988. p. 61–72. (Lecture Notes in Computer Science; volume 294).
  12. Damaschke P. The Hamiltonian circuit problem for circle graphs is NP-complete. Information Processing Letters. 1989;32(1): 1–2. DOI: 10.1016/0020-0190(89)90059-8.
  13. Garey MR, Johnson DS. Computers and intractability. A guide to the theory of NP-completeness. New York: W. H. Freeman and Company; 1979. X, 338 p.
  14. Valiant LG. Universality considerations in VLSI circuits. IEEE Transactions on Computers. 1981;C-30(2):135–140. DOI: 10.1109/TC.1981.6312176.
  15. Renegar J. On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals. Journal of Symbolic Computation. 1992;13(3):255–299. DOI: 10.1016/S0747-7171(10)80003-3.
  16. Pilz A, Welzl E. Order on order types. In: Arge L, Pach J, editors. 31st International symposium on computational geometry (SoCG’2015); 2015 June 22–25; Eindhoven, The Netherlands. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik; 2015. p. 285–299. (LIPIcs; volume 34). DOI: 10.4230/LIPIcs.SOCG.2015.285.
  17. Goodman JE, Pollack R, Sturmfels B. The intrinsic spread of a configuration in Rd. Journal of the American Mathematical Society. 1990;3(3):639–651. DOI: 10.1090/S0894-0347-1990-1046181-2.
Published
2021-04-12
Keywords: intersection graph, intersection graph of closed polygonal chains, regular graph, NP-completeness, polynomial-time reduction
How to Cite
Prochorov, N. P., & Dul, E. N. (2021). Graphs of intersections of closed polygonal chains. Journal of the Belarusian State University. Mathematics and Informatics, 1, 54-68. https://doi.org/10.33581/2520-6508-2021-1-54-68
Issue
No 1 (2021): Journal of the Belarusian State University. Mathematics and Informatics
Section
Discrete Mathematics and Mathematical Cybernetics

Copyright (c) 2021 Journal of the Belarusian State University. Mathematics and Informatics

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)