Refining the hierarchies of classes of geometric intersection graphs

zbMath1355.05092MaRDI QIDQ5892293

Sergio Cabello, Miha Jejčič

Publication date: 17 February 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p33

zbMATH Keywords

string graphssegment graphsgeometric intersection graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (11)

Embedding ray intersection graphs and global curve simplification ⋮ Intersection Graphs of Rays and Grounded Segments ⋮ Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded ⋮ Proper colorability of segment intersection graphs ⋮ Stick graphs with length constraints ⋮ Recognizing Stick Graphs with and without Length Constraints ⋮ On the speed of algebraically defined graph classes ⋮ Recognition and drawing of stick graphs ⋮ Homotopy type of circle graph complexes motivated by extreme Khovanov homology ⋮ On grounded \(\llcorner\)-graphs and their relatives ⋮ Outerstring Graphs are $\chi$-Bounded

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Triangle-free intersection graphs of line segments with large chromatic number
• Coloring intersection graphs of \(x\)-monotone curves in the plane
• Grid intersection graphs and order dimension
• String graphs. II: Recognizing string graphs is NP-hard
• String graphs. I: The number of critical nonstring graphs is infinite
• String graphs requiring exponential representations
• Unit disk graphs
• Thresholds for classes of intersection graphs
• Intersection graphs of segments
• Unit disk graph recognition is NP-hard
• Decidability of string graphs
• Integer realizations of disk and segment graphs
• The number of disk graphs
• On String Graph Limits and the Structure of a Typical String Graph
• Complexity of Some Geometric and Topological Problems
• Topics in Intersection Graph Theory
• Intersection Graphs of Rays and Grounded Segments
• Outerstring graphs are χ-bounded
• Every planar graph is the intersection graph of segments in the plane
• Near-Optimal Separators in String Graphs
• Topology of Thin Film RC Circuits
• Recognizing string graphs in NP

This page was built for publication: Refining the hierarchies of classes of geometric intersection graphs