Graphs of intersections of closed polygonal chains

MaRDI QIDQ6669632zbMATH OpenFDO

Authors Nikolaĭ Petrovich Prokhorov, Ekaterina Nikolaevna Dul'

Publication date 22 January 2025

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

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

zbMATH Keywords

intersection graphintersection graph of closed polygonal chainsNP-Completenesspolynomial-time reductionregular graph

Mathematics Subject Classification ID

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

Recommendations

• Graph Drawing
• String graphs. I: The number of critical nonstring graphs is infinite
• Polygon Graph Recognition
• String graphs. II: Recognizing string graphs is NP-hard
• The max clique problem in classes of string-graphs

Cites work

• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• scientific article; zbMATH DE number 4051024 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3220171 (Why is no real title available?)
• Intersection graphs of curves in the plane
• Intersection graphs of segments
• 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
• Order on order types
• String graphs. I: The number of critical nonstring graphs is infinite
• String graphs. II: Recognizing string graphs is NP-hard
• The complexity of domination problems in circle graphs
• The Hamiltonian circuit problem for circle graphs is NP-complete
• The Intrinsic Spread of a Configuration in R d
• Topology of Thin Film RC Circuits
• Universality considerations in VLSI 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)