Geodesic
Graphs of intersections of closed polygonal chains
Journal of the Belarusian State University. Mathematics and Informatics, Tome 1 (2021), pp. 54-68.

Voir la notice de l'article provenant de la source Math-Net.Ru

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\in \mathbb{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.
Keywords: intersection graph; intersection graph of closed polygonal chains; regular graph; $NP$-completeness; polynomial-time reduction. 
@article{BGUMI_2021_1_a4,
     author = {N. P. Prochorov and E. N. Dul},
     title = {Graphs of intersections of closed polygonal chains},
     journal = {Journal of the Belarusian State University. Mathematics and Informatics},
     pages = {54--68},
     publisher = {mathdoc},
     volume = {1},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/BGUMI_2021_1_a4/}
}
TY  - JOUR
AU  - N. P. Prochorov
AU  - E. N. Dul
TI  - Graphs of intersections of closed polygonal chains
JO  - Journal of the Belarusian State University. Mathematics and Informatics
PY  - 2021
SP  - 54
EP  - 68
VL  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/BGUMI_2021_1_a4/
LA  - ru
ID  - BGUMI_2021_1_a4
ER  - 
%0 Journal Article
%A N. P. Prochorov
%A E. N. Dul
%T Graphs of intersections of closed polygonal chains
%J Journal of the Belarusian State University. Mathematics and Informatics
%D 2021
%P 54-68
%V 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/BGUMI_2021_1_a4/
%G ru
%F BGUMI_2021_1_a4
N. P. Prochorov; E. N. Dul. Graphs of intersections of closed polygonal chains. Journal of the Belarusian State University. Mathematics and Informatics, Tome 1 (2021), pp. 54-68. http://geodesic.mathdoc.fr/item/BGUMI_2021_1_a4/

[1] F. W. Sinden, “Topology of thin film RC circuits”, The Bell System Technical Journal, 45(9) (1966), 1639–1662 | DOI | Zbl

[2] G. Ehrlich, S. Even, R. E. Tarjan, “Intersection graphs of curves in the plane”, Journal of Combinatorial Theory, 21(1) (1976), 8–20 | DOI | MR | Zbl

[3] J. Chalopin, D. Goncalves, “Every planar graph is the intersection graph of segments in the plane: extended abstract”, Proceedings of the Forty-first annual ACM symposium on theory of computing (Bethesda, Maryland, USA), Association for Computing Machinery, New York, 2009, 631–638 | DOI | Zbl

[4] J. Kratochvil, J. Matousek, “Intersection graphs of segments”, Journal of Combinatorial Theory, 62(2) (1994), 289–315 | DOI | MR | Zbl

[5] J. Kratochvil, “String graphs. Recognizing string graphs is NP-hard”, Journal of Combinatorial Theory, 52(1) (1991), 67–78 | DOI | MR | Zbl

[6] O. Ore, “Grafy i ikh primenenie”, Mir, Moskva, 1965, 174 | Zbl

[7] J. Kratochvil, “String graphs. The number of critical nonstring graphs is infinite”, Journal of Combinatorial Theory, 52(1) (1991), 53–66 | DOI | MR | Zbl

[8] C. Dangelmayr, “Intersection graphs of pseudosegments [dissertation]”, Freien Universitat Berlin, Berlin, 2010, 136 | MR

[9] D. B. Fuks, “Samoperesecheniya zamknutoi lomanoi”, Kvant, 1 (1988), 30–34

[10] J. M. Keil, “The complexity of domination problems in circle graphs”, Discrete Applied Mathematics, 42(1) (1993), 51–63 | DOI | MR | Zbl

[11] W. Unger, “On the k-colouring of circle-graphs”, STACS 88. 5th Annual symposium on theoretical aspects of computer science (Bordeaux, France), 294 (1988), 61–72, Springer-Verlag, Berlin | MR

[12] P. Damaschke, “The Hamiltonian circuit problem for circle graphs is NP-complete”, Information Processing Letters, 32(1) (1989), 1–2 | DOI | MR | Zbl

[13] M. R. Garey, D. S. Johnson, “Computers and intractability. A guide to the theory of NP-completeness”, 10, W H Freeman and Company, New York, 1979, 338 | MR

[14] L. G. Valiant, “Universality considerations in VLSI circuits”, IEEE Transactions on Computers, 30(2) (1981), 135–140 | DOI | MR | Zbl

[15] J. Renegar, “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, 13(3) (1992), 255–299 | DOI | MR | Zbl

[16] A. Pilz, E. Welzl, “Order on order types” (Eindhoven, The Netherlands), 31st International symposium on computational geometry (SoCG’2015), 34 (2015), 285–299, Schloss Dagstuhl – Leibniz-Zentrum fur Informatik, Wadern | DOI | MR

[17] J. E. Goodman, R. Pollack, B. Sturmfels, “The intrinsic spread of a configuration in Rd”, Journal of the American Mathematical Society, 3(3) (1990), 639–651 | DOI | MR | Zbl