{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:50:57Z","timestamp":1760244657399,"version":"build-2065373602"},"reference-count":9,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2022,12,12]],"date-time":"2022-12-12T00:00:00Z","timestamp":1670803200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>We study classes of geometric graphs, which all correspond to the following structural characteristic. For each instance of a vertex set drawn from a universe of possible vertices, each pair of vertices is either required to be connected, forbidden to be connected, or existence or non-existence of an edge is undetermined. The conditions which require or forbid edges are universally quantified predicates defined over the vertex pair, and optionally over existence or non-existence of another edge originating at the vertex pair. We consider further a set of simple graph transformations, where the existence of an edge between two vertices is logically determined by the existence or non-existence of directed edges between both vertices in the original graph. We derive and prove the correctness of a logical expression, which is a necessary and sufficient condition for containedness relations between graph classes that are described this way. We apply the expression on classes of geometric graphs, which are used as theoretical wireless network graph models. The models are constructed from three base class types and intersection combinations of them, with some considered directly and some considered as symmetrized variants using two of the simple graph transformations. Our study then goes systematically over all possible graph classes resulting from those base classes and all possible simple graph transformations. We derive automatically containedness relations between those graph classes. Moreover, in those cases where containedness does not hold, we provide automatically derived counter examples.<\/jats:p>","DOI":"10.3390\/info13120578","type":"journal-article","created":{"date-parts":[[2022,12,13]],"date-time":"2022-12-13T03:32:32Z","timestamp":1670902352000},"page":"578","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Automatically Testing Containedness between Geometric Graph Classes defined by Inclusion, Exclusion, and Transfer Axioms under Simple Transformations"],"prefix":"10.3390","volume":"13","author":[{"given":"Lucas","family":"B\u00f6ltz","sequence":"first","affiliation":[{"name":"Faculty of Computer Science, Universitiy of Koblenz-Landau, 56070 Koblenz, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hannes","family":"Frey","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, Universitiy of Koblenz-Landau, 56070 Koblenz, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,12,12]]},"reference":[{"key":"ref_1","unstructured":"Frey, H., and B\u00f6ltz, L. (2021, January 10\u201312). Automatically Testing Containedness between Geometric Graph Classes defined by Inclusion, Exclusion and Transfer Axioms. Proceedings of the 33rd Canadian Conference on Computational Geometry, CCCG 2021, Halifax, NS, Canada."},{"key":"ref_2","unstructured":"Gabbay, D.M., Schmidt, R.A., and Szalas, A. (2008). Studies in logic: Mathematical logic and foundations. Second-Order Quantifier Elimination\u2014Foundations, Computational Aspects and Applications, College Publications."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF01190829","article-title":"Refutational Theorem Proving for Hierarchic First-Order Theories","volume":"5","author":"Bachmair","year":"1994","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1002\/wcm.108","article-title":"Robust position-based routing in wireless ad hoc networks with irregular transmission ranges","volume":"3","author":"Fraigniaud","year":"2003","journal-title":"Wirel. Commun. Mob. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"715","DOI":"10.1007\/s11276-007-0045-6","article-title":"Ad hoc networks beyond unit disk graphs","volume":"14","author":"Kuhn","year":"2008","journal-title":"Wirel. Netw."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1267","DOI":"10.1109\/TMC.2006.139","article-title":"The k-Neighbors Approach to Interference Bounded and Symmetric Topology Control in Ad Hoc Networks","volume":"5","author":"Blough","year":"2006","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1109\/TNET.2008.926506","article-title":"Algorithmic Models of Interference in Wireless Ad Hoc and Sensor Networks","volume":"17","author":"Wattenhofer","year":"2009","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"25:1","DOI":"10.1145\/1807048.1807054","article-title":"Localized spanner construction for Ad Hoc networks with variable transmission range","volume":"7","author":"Peleg","year":"2010","journal-title":"ACM Trans. Sens. Netw."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1016\/j.adhoc.2004.08.004","article-title":"Robust position-based routing for wireless ad hoc networks","volume":"3","author":"Moaveninejad","year":"2005","journal-title":"Ad Hoc Netw."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/13\/12\/578\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:39:54Z","timestamp":1760146794000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/13\/12\/578"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,12]]},"references-count":9,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2022,12]]}},"alternative-id":["info13120578"],"URL":"https:\/\/doi.org\/10.3390\/info13120578","relation":{},"ISSN":["2078-2489"],"issn-type":[{"type":"electronic","value":"2078-2489"}],"subject":[],"published":{"date-parts":[[2022,12,12]]}}}