Geometric Intersection Graphs: Do Short Cycles Help?
DOI10.1007/978-3-540-73545-8_14zbMATH Open1206.05069OpenAlexW1480764610MaRDI QIDQ3608838FDOQ3608838
Authors: Jan Kratochvíl, Martin Pergel 
Publication date: 6 March 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-73545-8_14
Recommendations
- Approximation Algorithms for Geometric Intersection Graphs
- All-pairs shortest paths in geometric intersection graphs
- All-pairs shortest paths in geometric intersection graphs
- On the Intersections of Longest Cycles in a Graph
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Hop-spanners for geometric intersection graphs
- Refining the hierarchies of classes of geometric intersection graphs
- Refining the hierarchies of classes of geometric intersection graphs
- A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
- A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62)
Cited In (7)
- Finding geometric representations of apex graphs is NP-hard
- Graph Drawing
- On unit grid intersection graphs and several other intersection graph classes
- Complexity of some geometric and topological problems
- Finding geometric representations of apex graphs is \textsf{NP}-hard
- Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
- Testing bipartiteness of geometric intersection graphs
This page was built for publication: Geometric Intersection Graphs: Do Short Cycles Help?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608838)
