Testing bipartiteness of geometric intersection graphs

DOI10.1145/1497290.1497291zbMath1445.05100arXivcs/0307023OpenAlexW2052184512WikidataQ56209807 ScholiaQ56209807MaRDI QIDQ4962781

David Eppstein

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0307023

zbMATH Keywords

bipartite graphintersection graphgraph coloringminimum spanning treeline segmentsdisksgeometric thicknesscoin graphHopcroft's problem

Mathematics Subject Classification ID

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

Related Items (3)

Listing all spanning trees in Halin graphs — sequential and Parallel view ⋮ Shortest paths in intersection graphs of unit disks ⋮ Geometric biplane graphs. I: Maximal graphs

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