Graphs of intersections of closed polygonal chains

MaRDI QIDQ6669632

Ekaterina Nikolaevna Dul', Nikolaĭ Petrovich Prokhorov

Publication date: 22 January 2025

Published in: Zhurnal Belorusskogo Gosudarstvennogo Universiteta. Matematika. Informatika (Search for Journal in Brave)

zbMATH Keywords

intersection graphregular graphpolynomial-time reductionNP-Completenessintersection graph of closed polygonal chains

Mathematics Subject Classification ID

Distance in graphs (05C12) Vertex degrees (05C07) Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• String graphs. II: Recognizing string graphs is NP-hard
• String graphs. I: The number of critical nonstring graphs is infinite
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• The complexity of domination problems in circle graphs
• Intersection graphs of curves in the plane
• Intersection graphs of segments
• The Hamiltonian circuit problem for circle graphs is NP-complete
• The Intrinsic Spread of a Configuration in R d
• Universality considerations in VLSI circuits
• Every planar graph is the intersection graph of segments in the plane
• Order on Order Types
• Topology of Thin Film RC Circuits

This page was built for publication: Graphs of intersections of closed polygonal chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6669632)