Testing bipartiteness of geometric intersection graphs

zbMATH Open1318.05078MaRDI QIDQ5501348FDOQ5501348

Authors: David Eppstein 

Publication date: 3 August 2015

Recommendations

• Testing bipartiteness of geometric intersection graphs
• Efficient Algorithms for Geometric Graph Search Problems
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Geometric Intersection Graphs: Do Short Cycles Help?
• Intersection graphs of segments

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (5)

• Maximum bipartite subgraphs of geometric intersection graphs
• Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs
• 3-coloring arrangements of line segments with 4 slopes is hard
• Edges and switches, tunnels and bridges
• Testing bipartiteness of geometric intersection graphs

This page was built for publication: Testing bipartiteness of geometric intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501348)