Automatically Testing Containedness between Geometric Graph Classes defined by Inclusion, Exclusion, and Transfer Axioms under Simple Transformations
Abstract
:1. Introduction
2. Geometric Graph Models
3. Axiomatic Description of Graph Classes
3.1. Inclusion, Exclusion, and Transfer Predicates
3.2. Simple Graph Class Transformations
4. Proving Graph Class Containedness Relations
4.1. General Properties
- The null graph satisfies .
- Let satisfy . Every subgraph induced by satisfies .
- The null graph satisfies .
- If γ is simple and if satisfies , then every subgraph induced by satisfies .
4.2. Axiomatization for
4.3. Minimal Counter Examples
4.4. Expressions for Proving Subclass Relations
5. Example Application
5.1. Manual Application of the Derived Concept
5.2. Automatically Derived Graph Class Relations
- =
- The classes are the same
- ⊂
- The class is contained in the other class but the classes are not the same
- ⊃
- The class contains the other class but the classes are not the same
- ×
- Neither of the two classes is contained in the others, (by lemmas 1 and 2 each of the studied graph classes contain at least the null graph. Thus, none of the considered graph classes are disjoint).
6. Conclusions
Author Contributions
Funding
Institutional Review Board Statement
Informed Consent Statement
Data Availability Statement
Acknowledgments
Conflicts of Interest
Appendix A. Automatically Derived Containedness Relations
Appendix B. Automatically Derived Counter Examples
Appendix C. Proof of Lemma 4
References
- Frey, H.; Böltz, L. Automatically Testing Containedness between Geometric Graph Classes defined by Inclusion, Exclusion and Transfer Axioms. In Proceedings of the 33rd Canadian Conference on Computational Geometry, CCCG 2021, Halifax, NS, Canada, 10–12 August 2021; pp. 127–138. [Google Scholar]
- Gabbay, D.M.; Schmidt, R.A.; Szalas, A. Studies in logic: Mathematical logic and foundations. In Second-Order Quantifier Elimination—Foundations, Computational Aspects and Applications; College Publications: Rickmansworth, UK, 2008; Volume 12. [Google Scholar]
- Bachmair, L.; Ganzinger, H.; Waldmann, U. Refutational Theorem Proving for Hierarchic First-Order Theories. Appl. Algebra Eng. Commun. Comput. 1994, 5, 193–212. [Google Scholar] [CrossRef]
- Barrière, L.; Fraigniaud, P.; Narayanan, L.; Opatrny, J. Robust position-based routing in wireless ad hoc networks with irregular transmission ranges. Wirel. Commun. Mob. Comput. 2003, 3, 141–153. [Google Scholar] [CrossRef]
- Kuhn, F.; Wattenhofer, R.; Zollinger, A. Ad hoc networks beyond unit disk graphs. Wirel. Netw. 2008, 14, 715–729. [Google Scholar] [CrossRef]
- Blough, D.M.D.; Leoncini, M.; Resta, G.; Santi, P. The k-Neighbors Approach to Interference Bounded and Symmetric Topology Control in Ad Hoc Networks. IEEE Trans. Mob. Comput. 2006, 5, 1267–1282. [Google Scholar] [CrossRef]
- von Rickenbach, P.; Wattenhofer, R.; Zollinger, A. Algorithmic Models of Interference in Wireless Ad Hoc and Sensor Networks. IEEE/ACM Trans. Netw. 2009, 17, 172–185. [Google Scholar] [CrossRef]
- Peleg, D.; Roditty, L. Localized spanner construction for Ad Hoc networks with variable transmission range. ACM Trans. Sens. Netw. 2010, 7, 25:1–25:14. [Google Scholar] [CrossRef] [Green Version]
- Moaveninejad, K.; Song, W.Z.; Li, X.Y. Robust position-based routing for wireless ad hoc networks. Ad Hoc Netw. 2005, 3, 546–559. [Google Scholar] [CrossRef]
0 | 0 | 1 | 1 | ||||
---|---|---|---|---|---|---|---|
Name | Symbol | 0 | 1 | 0 | 1 | Symmetry | |
Symmetric subgraph | 0 | 0 | 0 | 1 | Symmetric | ||
Symmetric supergraph | 0 | 1 | 1 | 1 | Symmetric | ||
xor graph | 0 | 1 | 1 | 0 | Symmetric | ||
Empty graph | 0 | 0 | 0 | 0 | Symmetric | ||
Identity graph | 0 | 0 | 1 | 1 | |||
Reversed graph | 0 | 1 | 0 | 1 | |||
Outgoing directed subgraph | 0 | 0 | 1 | 0 | Directed | ||
Incoming directed subgraph | 0 | 1 | 0 | 0 | Directed |
0 | 0 | 1 | 1 | |||
---|---|---|---|---|---|---|
Symbol | 0 | 1 | 0 | 1 | Symmetry | |
1 | 1 | 1 | 0 | Symmetric | ||
1 | 0 | 0 | 0 | Symmetric | ||
1 | 0 | 0 | 1 | Symmetric | ||
1 | 1 | 1 | 1 | Symmetric | ||
1 | 1 | 0 | 0 | |||
1 | 0 | 1 | 0 | |||
1 | 1 | 0 | 1 | Complementary directed | ||
1 | 0 | 1 | 1 | Complementary directed |
Edge Inclusion and Exclusion Implications | ||||
---|---|---|---|---|
⇒ | ⊥ | 1 | ||
⇒ | ⊤ | |||
⇒ | ⊤ | 1 | ||
⇒ | ⊥ | |||
⇒ | 3 | |||
⇒ | ||||
⇒ | 3 | |||
⇒ | ||||
⇒ | 4 | |||
⇒ | ||||
⇒ | 4 | |||
⇒ | ||||
⇒ | 4 | |||
⇒ | ||||
⇒ | 4 | |||
⇒ | ||||
⇒ | 3 | |||
⇒ | ||||
⇒ | 3 | |||
⇒ | ||||
⇒ | 4 | |||
⇒ | ||||
⇒ | 4 | |||
⇒ | ||||
⇒ | 4 | |||
⇒ | ||||
⇒ | 4 | |||
⇒ | ||||
Edge Inclusion and Exclusion Implications | |||
---|---|---|---|
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= |
Edge Inclusion and Exclusion Implications | |||
---|---|---|---|
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= | |||
= |
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. |
© 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
Share and Cite
Böltz, L.; Frey, H. Automatically Testing Containedness between Geometric Graph Classes defined by Inclusion, Exclusion, and Transfer Axioms under Simple Transformations. Information 2022, 13, 578. https://doi.org/10.3390/info13120578
Böltz L, Frey H. Automatically Testing Containedness between Geometric Graph Classes defined by Inclusion, Exclusion, and Transfer Axioms under Simple Transformations. Information. 2022; 13(12):578. https://doi.org/10.3390/info13120578
Chicago/Turabian StyleBöltz, Lucas, and Hannes Frey. 2022. "Automatically Testing Containedness between Geometric Graph Classes defined by Inclusion, Exclusion, and Transfer Axioms under Simple Transformations" Information 13, no. 12: 578. https://doi.org/10.3390/info13120578
APA StyleBöltz, L., & Frey, H. (2022). Automatically Testing Containedness between Geometric Graph Classes defined by Inclusion, Exclusion, and Transfer Axioms under Simple Transformations. Information, 13(12), 578. https://doi.org/10.3390/info13120578