On forbidden induced subgraphs for unit disk graphs

DOI10.1007/S00454-018-9968-1zbMATH Open1394.05105arXiv1602.08148OpenAlexW2963467716MaRDI QIDQ724944FDOQ724944

Victor Zamaraev, Aistis Atminas

Publication date: 26 July 2018

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: A unit disk graph is the intersection graph of disks of equal radii in the plane. The class of unit disk graphs is hereditary, and therefore admits a characterization in terms of minimal forbidden induced subgraphs. In spite of quite active study of unit disk graphs very little is known about minimal forbidden induced subgraphs for this class. We found only finitely many minimal non unit disk graphs in the literature. In this paper we study in a systematic way forbidden induced subgraphs for the class of unit disk graphs. We develop several structural and geometrical tools, and use them to reveal infinitely many new minimal non unit disk graphs. Further we use these results to investigate structure of co-bipartite unit disk graphs. In particular, we give structural characterization of those co-bipartite unit disk graphs whose edges between parts form a C4-free bipartite graph, and show that bipartite complements of these graphs are also unit disk graphs. Our results lead us to propose a conjecture that the class of co-bipartite unit disk graphs is closed under bipartite complementation.

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

Recommendations

• The number of disk graphs
• Unit disk graphs
• Partial characterizations of circle graphs
• Counting disk graphs
• scientific article; zbMATH DE number 759636

zbMATH Keywords

forbidden induced subgraphsunit disk graphsco-bipartite graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

Cites Work

• Unit disk graph recognition is NP-hard
• Efficient graph representations
• The strong perfect graph theorem
• Asteroidal Triple-Free Graphs
• On orthogonal ray graphs
• Implicat Representation of Graphs
• List homomorphisms and circular arc graphs
• Simple heuristics for unit disk graphs
• Integer realizations of disk and segment graphs
• Implicit representations and factorial properties of graphs
• Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
• On the recognition of unit disk graphs and the distance geometry problem with ranges
• The number of disk graphs

Cited In (3)

• Title not available (Why is that?)
• Unit ball graphs on geodesic spaces
• Global Rigidity of Unit Ball Graphs

This page was built for publication: On forbidden induced subgraphs for unit disk graphs

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