Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.01383 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916984959008768 |
|---|---|
| author | Pegden, Wesley Wang, Eric |
| author_facet | Pegden, Wesley Wang, Eric |
| contents | We introduce and study two Maker-Breaker-like games for constructing planar graphs: the edge drawing game, where two players take turns drawing non-intersecting edges between points in the plane, and the circle packing game, where the players take turns placing disjoint circles in the plane. Both games produce planar graphs: the edge drawing game results in a plane graph drawing, and the circle packing game yields a planar graph via the contact graph of the packing. For both games, we give necessary conditions under which a given planar graph can be constructed. We also show that the two games are indeed different by giving a class of graphs which can be constructed in one but not the other. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_01383 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Competitively Constructed Planar Graphs Pegden, Wesley Wang, Eric Combinatorics We introduce and study two Maker-Breaker-like games for constructing planar graphs: the edge drawing game, where two players take turns drawing non-intersecting edges between points in the plane, and the circle packing game, where the players take turns placing disjoint circles in the plane. Both games produce planar graphs: the edge drawing game results in a plane graph drawing, and the circle packing game yields a planar graph via the contact graph of the packing. For both games, we give necessary conditions under which a given planar graph can be constructed. We also show that the two games are indeed different by giving a class of graphs which can be constructed in one but not the other. |
| title | Competitively Constructed Planar Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2510.01383 |