Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2409.11249 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910608097542144 |
|---|---|
| author | Tilley, James Wagon, Stan Weisstein, Eric |
| author_facet | Tilley, James Wagon, Stan Weisstein, Eric |
| contents | Considering regions in a map to be adjacent when they have nonempty intersection (as opposed to the traditional view requiring intersection in a linear segment) leads to the concept of a facially complete graph: a plane graph that becomes complete when edges are added between every two vertices that lie on a face. Here we present a complete catalog of facially complete graphs: they fall into seven types. A consequence is that if q is the size of the largest face in a plane graph G that is facially complete, then G has at most Floor[3/2 q] vertices. This bound was known, but our proof is completely different from the 1998 approach of Chen, Grigni, and Papadimitriou. Our method also yields a count of the 2-connected facially complete graphs with n vertices. We also show that if a plane graph has at most two faces of size 4 and no larger face, then the addition of both diagonals to each 4-face leads to a graph that is 5-colorable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_11249 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Catalog of Facially Complete Graphs Tilley, James Wagon, Stan Weisstein, Eric Combinatorics 05C10, 05C15 Considering regions in a map to be adjacent when they have nonempty intersection (as opposed to the traditional view requiring intersection in a linear segment) leads to the concept of a facially complete graph: a plane graph that becomes complete when edges are added between every two vertices that lie on a face. Here we present a complete catalog of facially complete graphs: they fall into seven types. A consequence is that if q is the size of the largest face in a plane graph G that is facially complete, then G has at most Floor[3/2 q] vertices. This bound was known, but our proof is completely different from the 1998 approach of Chen, Grigni, and Papadimitriou. Our method also yields a count of the 2-connected facially complete graphs with n vertices. We also show that if a plane graph has at most two faces of size 4 and no larger face, then the addition of both diagonals to each 4-face leads to a graph that is 5-colorable. |
| title | A Catalog of Facially Complete Graphs |
| topic | Combinatorics 05C10, 05C15 |
| url | https://arxiv.org/abs/2409.11249 |