Intersection Graphs of Rays and Grounded Segments

DOI10.7155/jgaa.00470zbMath1394.05080arXiv1612.03638OpenAlexW2950641361WikidataQ129510890 ScholiaQ129510890MaRDI QIDQ4585058

Tillmann Miltzow, Birgit Vogtenhuber, Jean Cardinal, Casey Tompkins, Stefan Felsner

Publication date: 6 September 2018

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1612.03638

zbMATH Keywords

intersection graphs of downward raysintersection graphs of grounded segments

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Finding a Maximum Clique in a Grounded 1-Bend String Graph ⋮ Embedding ray intersection graphs and global curve simplification ⋮ Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded ⋮ On the complexity of recognizing Stick, BipHook and max point-tolerance graphs ⋮ Stick graphs with length constraints ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ Recognizing Stick Graphs with and without Length Constraints ⋮ On the speed of algebraically defined graph classes ⋮ Computing maximum independent set on outerstring graphs and their relatives ⋮ On grounded \(\llcorner\)-graphs and their relatives ⋮ Outerstring Graphs are $\chi$-Bounded ⋮ Graph Classes and Forbidden Patterns on Three Vertices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The clique problem in ray intersection graphs
• Integer programming and combinatoral optimization. 15th international conference, IPCO 2011, New York, NY, USA, June 15--17, 2011. Proceedings
• On orthogonal ray graphs
• An algorithm for the maximum weight independent set problem on outerstring graphs
• Grid intersection graphs and order dimension
• On orthogonal ray trees
• Reconnaissance des graphes de cordes
• 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
• Intersection graphs of curves in the plane
• Intersection graphs of segments
• Colouring relatives of intervals on the plane. II: Intervals and rays in two directions
• Coloring relatives of intervals on the plane. I: Chromatic number versus girth
• Graph drawing. 17th international symposium, GD 2009, Chicago, IL, USA, September 22--25, 2009. Revised papers
• Theory and applications of models of computation. 11th annual conference, TAMC 2014, Chennai, India, April 11--13, 2014. Proceedings
• The Order Dimension of Planar Maps Revisited
• Topics in Intersection Graph Theory
• Outerstring graphs are χ-bounded
• Every planar graph is the intersection graph of segments in the plane
• Topology of Thin Film RC Circuits
• Refining the hierarchies of classes of geometric intersection graphs
• Recognizing string graphs in NP