Intersection Graphs of Rays and Grounded Segments
From MaRDI portal
Publication:4585058
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
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