Geometric Intersection Graphs: Do Short Cycles Help?

DOI10.1007/978-3-540-73545-8_14MaRDI QIDQ3608838zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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

Cited in

(7)

• Finding geometric representations of apex graphs is NP-hard
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
• Complexity of some geometric and topological problems
• Graph Drawing
• Testing bipartiteness of geometric intersection graphs
• Finding geometric representations of apex graphs is \textsf{NP}-hard
• On unit grid intersection graphs and several other intersection graph classes

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)