Testing bipartiteness of geometric intersection graphs

MaRDI QIDQ5501348zbMATH OpenFDO

Authors David Eppstein

Publication date 3 August 2015

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)

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

Cited in

(5)

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

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)